# Chromatic number $χ(G) > k$ implies existence of path of length $k$

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??

-
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

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.

-
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