Prescribed edge in cubic graph
Task number: 4048
Let \( G \) be a cubic graph without bridges. Prove that for each of its edges there is a perfect matching that contains it.
Hint
Similarly to the task where the matching does not contain a specified edge. The graph must have an even number of vertices. Remove both vertices that form the ends of the edge.
Solution
Let’s denote the graph by \( G \) and the prescribed edge by \( uv \). By \( G’\) we denote the graph \( G \) after removing the vertices \( u, v \).
For a contradiction, suppose that \( G’\) does not have a perfect matcing and therefore Tutte’s condition does not hold. Hence there exists \( S’\subseteq V (G’) \) that \( | S’ | < C_o (G’, S’) \).
Cubic graphs such as \( G \) have an even number of vertices according to the principle of evenness, and the same is true for \( G’\). As a consequence, the size of the \( S’\) and the number of odd components have the same parity. Therefore, the inequality \( | S’| < C_o (G’, S’) \) can be strengthened to \( | S’| \le C_o (G’, S’) - 2 \).
To obtain the cut \( S \) in the graph \( G \), we choose \( S = S’\cup \{u, v \} \). The complement of \( S \) in \( G \) is the same as the complement of \( S’\) in \( G'\), therefore \( C_o (G, S) = C_o (G’, S’) \).
According to the principle of evenness, an odd number of edges should lead to the odd components of the graph \( G \). Because the graph \( G \) has no bridge, at least three edges connect each odd component.
Because \( G \) is cubic, from \( S’\) stems at most \(3|S’|\) edges. After adding the vertices \( u \) and \( v \), we get that from \( S \) stems at most \( 3 |S’|+4 \) edges.
Therefore, for the number of edges \( \#e \) incident with \( S \) we get that: \[ 3 (C_o (G, S)) \le \#e \le 3 | S’| +4 \le 3 (C_o (G’, S’) - 2) +4 = 3 (C_o (G, S)) -2 \] which is the desired contradiction.
