Kvant Math Problem 1147
The condition says that every closed path contains an even number of red edges.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m08s
Source on kvant.digital
Problem
Several points are given, connected by segments of two colors: some pairs of points are connected by blue segments, and some other pairs by red segments. It is known that in any closed path consisting of several segments, the number of red segments is even. Prove that all points can be divided into two sets so that each red segment connects points from different sets, and each blue segment connects points from the same set.
Exploration
The condition says that every closed path contains an even number of red edges. This resembles a parity condition. If one thinks of a blue edge as having parity $0$ and a red edge as having parity $1$, then the condition says that the sum of edge parities around every cycle is $0$ modulo $2$.
The desired partition into two sets also has a parity interpretation. If vertices are assigned labels $0$ and $1$, then blue edges should join vertices with the same label, while red edges should join vertices with different labels. For an edge $uv$, this means
$$\ell(u)+\ell(v)\equiv c(uv)\pmod 2,$$
where $c(uv)=0$ for blue and $c(uv)=1$ for red.
A natural idea is to choose one vertex in each connected component and define the label of any other vertex as the parity of the number of red edges along a path from the chosen vertex to that vertex. The crucial question is whether this parity depends on the chosen path.
Suppose there are two paths from the base vertex to the same vertex. Traversing the first path and then the second in reverse produces a closed path. By hypothesis, that closed path contains an even number of red edges. Hence the two paths contain red edges of the same parity. This makes the definition well posed.
The step most likely to hide an error is the passage from the parity condition on closed paths to the independence of path parity. That point must be proved carefully.
Problem Understanding
We are given a graph whose edges are colored red or blue. The graph need not be connected. Every closed path contains an even number of red edges.
We must prove that the vertices can be partitioned into two sets such that every red edge joins vertices from different sets and every blue edge joins vertices from the same set.
This is a Type B problem. The statement is purely existential and asks for a proof.
The core difficulty is constructing the partition and proving that it is well defined. The given condition concerns cycles, whereas the required conclusion concerns all edges. The bridge between them is the parity of the number of red edges along a path.
Proof Architecture
Lemma 1. In a connected component, any two paths joining the same pair of vertices contain numbers of red edges of the same parity.
Sketch. The union of one path and the reverse of the other is a closed path, whose number of red edges is even.
Lemma 2. After choosing a base vertex in a connected component, the parity of the number of red edges on a path from the base vertex to any vertex is well defined.
Sketch. This is exactly Lemma 1.
Lemma 3. If vertices are labeled by these path parities, then for every edge $uv$, the labels satisfy $\ell(u)+\ell(v)\equiv 0\pmod 2$ when $uv$ is blue and $\ell(u)+\ell(v)\equiv 1\pmod 2$ when $uv$ is red.
Sketch. Extend a path from the base vertex to $u$ by the edge $uv$ and compare the resulting parity with the label of $v$.
The hardest direction is proving that the labeling is well defined. Lemma 1 is the point most likely to fail under scrutiny if handled carelessly.
Solution
Consider one connected component of the graph. Choose a vertex $O$ in that component.
For any vertex $V$ in the component, define $\ell(V)$ to be the parity of the number of red edges on a path from $O$ to $V$. Before this definition can be used, it must be shown that it does not depend on the chosen path.
Let $P_1$ and $P_2$ be two paths from $O$ to $V$. Traverse $P_1$ from $O$ to $V$ and then traverse $P_2$ in the reverse direction from $V$ back to $O$. This produces a closed path.
By hypothesis, every closed path contains an even number of red edges. The number of red edges on the resulting closed path is equal to the sum of the numbers of red edges on $P_1$ and $P_2$, because reversing a path does not change how many red edges it contains.
Hence
$$r(P_1)+r(P_2)\equiv 0 \pmod 2,$$
where $r(P)$ denotes the number of red edges on $P$.
Therefore
$$r(P_1)\equiv r(P_2)\pmod 2.$$
The parity is independent of the chosen path, so $\ell(V)$ is well defined.
Now divide the vertices of the component into two sets:
$$A={V:\ell(V)=0}, \qquad B={V:\ell(V)=1}.$$
It remains to verify the required property of every edge.
Let $uv$ be an edge. Choose a path $P$ from $O$ to $u$.
First suppose that $uv$ is blue. Then the path obtained by appending $uv$ to $P$ contains exactly the same number of red edges as $P$, because the added edge is not red. Hence the parity of the number of red edges on a path from $O$ to $v$ is the same as on a path from $O$ to $u$. By the definition of $\ell$,
$$\ell(v)=\ell(u).$$
Thus $u$ and $v$ belong to the same set.
Next suppose that $uv$ is red. Appending $uv$ to $P$ increases the number of red edges by $1$. Consequently,
$$\ell(v)\equiv \ell(u)+1 \pmod 2.$$
Hence
$$\ell(v)\neq \ell(u),$$
so $u$ and $v$ belong to different sets.
Thus every blue edge joins two vertices of the same set, and every red edge joins two vertices of different sets.
The argument applies independently to each connected component. Taking the resulting partitions together over all components yields a partition of all vertices of the graph with the required property.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is proving that $\ell(V)$ is well defined. If two paths $P_1$ and $P_2$ from $O$ to $V$ had different red parities, then $r(P_1)+r(P_2)$ would be odd. Traversing $P_1$ and then $P_2$ in reverse would give a closed path with an odd number of red edges, contradicting the hypothesis. The contradiction uses exactly the assumption about closed paths.
The second delicate step is the treatment of a blue edge. Let $P$ be a path from $O$ to $u$. Appending a blue edge adds zero red edges, so the parity remains unchanged. Since the parity defining $\ell(v)$ is independent of path choice, the particular path $P$ followed by $uv$ may be used to compute $\ell(v)$. Thus $\ell(v)=\ell(u)$.
The third delicate step is the treatment of a red edge. Appending a red edge changes the red count by exactly one. The parity is therefore reversed. This yields $\ell(v)\equiv\ell(u)+1\pmod 2$, which is precisely the statement that the endpoints lie in different sets.
Alternative Approaches
A different proof uses linear algebra over $\mathbb F_2$. Assign value $0$ to each blue edge and value $1$ to each red edge. The condition that every cycle contains an even number of red edges says that the sum of edge values around every cycle is $0$ in $\mathbb F_2$. In graph-theoretic language, the edge coloring defines a $1$-cocycle whose value on every cycle is zero.
Choose one vertex in each connected component and set its label to $0$. For any other vertex, define its label by summing the edge values along a path from the base vertex. The cycle condition guarantees path independence. Then the difference of the labels at the ends of an edge equals the value assigned to that edge, giving exactly the required partition.
The main proof is preferable because it avoids algebraic terminology and works directly with the parity interpretation that is already present in the statement.