0
$\begingroup$

We define :
$\chi'(G)$ is the minimum number of colors we need in order to color all edges of the graph $G$.

Assume that we have a graph like $G$ with $2k+1$ vertices and $|E(G)| \gt k\Delta(G)$.
Prove that $\chi'(G) \ge \Delta(G)+1$.

Note : By coloring, here I mean a proper coloring. So, no two adjacent edges have the same color.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

Note that $\chi'(G) \geq \Delta(G)$ be definition. So it is sufficient to prove the case that $\chi'(G) = \Delta(G)$ is impossible. I prove by contradiction below.

Proof: Assume $\chi'(G) = \Delta(G)$. We then have $$ |E(G)| > k \cdot \chi'(G) $$ By Pigeonhole principle, there exists a color $c$ such that at least $k + 1$ edges of $G$ are of color $c$. However, because two edges with same color can not have common end points, there are at most $\lfloor \frac{2k + 1}{2} \rfloor = k$ edges with same color. A contradiction. Q.E.D.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .