1
$\begingroup$

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.

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

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer... I wish I could accept it... $\endgroup$ Jun 26 at 6:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.