1
$\begingroup$

In the proof for the NP-completeness of Edge-colouring (paper), there is an intermediate result used called the parity condition, which is formulated in a lemma.

Quoting from the paper:


Let $G$ be a cubic, 3-edge colored graph and V' \subseteq V(G) a set of vertices in $G$. Let E' \subseteq E(G) be the set of edges of $G$ which connect V' to the remainder of the graph. If the number of edges of color $i$ in E' is $k_i$ ($i = 1, 2, 3$), then

$ k_1 \equiv k_2 \equiv k_3 \pmod 2 $

Proof. If $E_{12}$ is the set of edges of $G$ which are colored with color 1 or 2, the $E_{12}$ consists of a collection of cycles. Thus $E_{12}$ meets E' in an even number of edges, and so $k_1 + k_2 \equiv 0 \pmod 2$. Similarly $k_2 \equiv k_3 \pmod 2$. $\Box$


I'm having trouble getting the intuition for the proof. Why does $E_{12}$ necessarily consist of cycles? And why does that fact lead us that $E_{12}$ necessarily meets E' in an even number of edges?

1 Answers 1

2

Since $G$ is cubic (i.e., 3-regular) and 3-edge-colored, every vertex is adjacent to exactly one edge of each color. Therefore $E_{12}$ is 2-regular, and every edge in a finite 2-regular graph must be part of a cycle that is disjoint from the rest of the graph (start from the chosen edge, and continue following the only path you can without doubling back until you reach your starting point).

Assign, arbitrarily, a direction to each of the cycles in $E_{12}$. The cycle passes into V' exactly as many times as it passes out of V', so it contributes an even number of edges to E_{12}\cap E'.

  • 0
    Thank you! I was way off with my original thinking.2012-02-10