

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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?

share|cite|improve this question
up vote 2 down vote accepted

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'$.

share|cite|improve this answer
Thank you! I was way off with my original thinking. – Sami Lehtinen Feb 10 '12 at 19:53

Your Answer


