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

Question

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.

Answer 1

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.

Answer 2

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.