# How to prove Graph with $n$ vertices has Edge Chromatic Number no more than $n/2$ edges

Show that if $$G$$ is a graph with $$n$$ vertices, then no more than $$n/2$$ edges can be colored in the same color, in any edge coloring of $$G$$.

I know there are optimal cases satisfy the statement, e.g a circuit of $$n$$ vertices with an even $$n$$ .

However, I want the proof of above statement.
As we known, cases can only falsify a statement instead of verify it.

• Counterexample: $G=K_n$ where $n\gt2$, all edges colored red. Did you mean proper edge coloring?
– bof
Jun 26 at 1:15

Let $$G=(V,E)$$ by some graph, with $$n$$ vertices, and let $$c$$ by some edge-coloring of $$G$$.

Denote by $$i$$ some color in the coloring, and define a set $$A_i$$ to be the set of all vertices with adjacent edge colored in $$i$$:

$$A_i:=\{v\in V\mid \exists u\in V \ \ s.t \ \ (v,u)\in E\ \land\ c(v,u)=i \}$$

Notice $$A_i\subseteq V\implies\vert A_i\vert \leq n$$.

Prop: Let $$B_i:=\{e\in E\mid c(e)=i \}$$. Then $$2\vert B_i\vert= \vert A_i\vert$$.

Proof:

Define a function between every pair adjacent vertices $$u,v\in A_i$$, to $$(u,v)\in B_i$$.

This map is a bijection (otherwise $$c$$ would not be a proper coloring), and therefore there are at most $$2$$ vertices in $$A_i$$ for every edge in $$B_i$$.

This proves the inequality.

Remark: Proving this map is a bijection is not hard and is mostly the core of the proof.

For any color, say red, let $$\{e_1,e_2,\dots,e_m\}$$ be the set of edges colored red. Each edge has two endpoints, say $$e_i$$ has endpoints $$v^i_1$$ and $$v^i_2$$. Then the list of vertices $$v^1_1,v^1_2,v^2_1,v^2_2,\dots,v^m_1,v^m_2$$ must not have any repeats. If there where some $$v^i_1=v^j_2$$, or $$v^i_1=v^j_1$$, then edges $$e_i$$ and $$e_j$$ would have a common endpoint, contradicting the fact that they were colored red. Therefore, above is a list of $$2m$$ distinct vertices. There are only $$n$$ vertices in $$V$$, so $$2m\le n$$, so at most $$n/2$$ edges are colored red.

• Thanks for the answer... I wish I could accept it... Jun 26 at 6:10