# Prove that a graph with given restraints, edges coloring is of size $\Delta$ + 1

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!

• 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$. – bof May 28 at 22:18
• I understand what you say but never thought of it. Thank you, I will try it again! – MTLaurentys May 28 at 22:22