6
$\begingroup$

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

  • 1
    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.2012-11-24

3 Answers 3