Prove that if $G$ is a

  • simple graph of order $n$,

  • with $n$ odd,

  • with $|E| > \frac{1}{2}(n-1)\Delta(G)$

then $\chi'(G) > \Delta(G)$.

I believe I have to prove that this amount of edges imply a certain structure in the graph. And then show that this structure forces $\Delta +1$ colors. I do not know why it has to be odd, as I could not think of the given structures.

Drawing a graph with $n=5, \Delta=3, |E| = 7$ I could see the result. I see there a two cycles of with three edges adjacent with a cycle of four edges, but I cannot prove or formalize that.

Any help is appreciated!

  • 2
    $\begingroup$ It's not that complicated. Hint. If $G$ is a graph of order $n$, then in a proper edge coloring of $G$, there are at most $\lfloor n/2\rfloor$ edges of each color, so $|E|\le\chi'(G)\lfloor n/2\rfloor$. $\endgroup$ – bof May 28 at 22:18
  • $\begingroup$ I understand what you say but never thought of it. Thank you, I will try it again! $\endgroup$ – MTLaurentys May 28 at 22:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.