Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that if $G$ is a loopless graph, $k≥1$ is an integer and $χ(G) > k$ then $G$ has a path with $k$ edges.

So, we can assume WLOG that $G$ is connected. we're looking for a path $P$ where $|V(P)| = k+1 $ and $|E(P)| = k.$ I'm stuck with this question. I know that $χ(G) < d(G) + 1$ where $d(G)$ is the maximum vertex degree of $G$. If $χ(G)= k+1$ , then there must be at least $k+1$ vertices of degree $> k$. I'm not sure how to take it from there, or if I'm even in the right direction. Can anyone please help??

share|improve this question
Please do not change the question you have asked. If you want, you can ask another question. It is extremely confusing to alter a question to which an answer has already been provided. –  EuYu Nov 24 '12 at 8:58
add comment

1 Answer

Let $\ell$ denote the length of the longest path in $G$ with chromatic number $\chi > k$. The minimal degree of $G$ satisfies $\delta \ge \chi - 1 \ge k$ and the longest path satisfies $\ell \ge \delta$. Therefore $\ell \ge k$.

Edit: I made a small mistake in the above, but the idea is the same. Let $G$ be a $\chi$-chromatic graph where $ \chi > k$. Then $G$ contains a $\chi$-critical subgraph $H\subseteq G$. For the $\chi$-critical graph $H$, we have $\delta_H \ge \chi - 1$ where $\delta_H$ is the smallest vertex degree of $H$.

We know that a graph with least degree $\delta$ necessarily has a path of length at least $\delta$ so it follows that the longest path of $H$ is of length at least $$\delta_H \ge \chi - 1 \ge k$$ So $H$ contains a path of length at least $k$ and therefore $G$ also contains the same path.

share|improve this answer
isn't the inequality d(G) > χ−1 , where d(G) is the maximal degree, as opposed to $\delta \ge \chi - 1 \ge k$ ?? –  Gogol Nov 17 '12 at 1:05
$\delta$ is the least degree. Let me elaborate a bit more. –  EuYu Nov 17 '12 at 1:07
thank you so much! i don't understand how we can deduce that if G is χ-chromatic then there is an χ-critical subgraph H⊆G ? also how do we know δH≥χ−1 ? are theres identities i just don't know about? –  Gogol Nov 17 '12 at 1:55
Short of adding the proofs of those two properties, there's nothing much I can do. If you have access to the book Pearls in Graph Theory: A Comprehensive Introduction by Hartsfield and Ringel then the results are proven in Chapter $2$. –  EuYu Nov 17 '12 at 2:29
Take a look at section $14.2$ in this book –  EuYu Nov 17 '12 at 2:37
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.