## Two edges omitted in cubic graph

Prove that for every pair of edges of a cubic graph without bridges there is a perfect matching, which does not contain them.

• #### Hint

Proceed in the same way as for a single omitted edge.

• #### Solution

If the edges are adjacent, we use the fact that there is a pairing that contains a third edge incident with the vertex common to the two prescribed edges.

Let the graph be denoted by $$G$$ and the edges by $$e, f$$. Let us denote by $$G’$$ the graph obtained from $$G$$ by removing both edges $$e, f$$.

For a contradiction, let $$G’$$ do not have a perfect matching. Thus it violates Tutte’s condition and there is a $$S \subset V (G)$$, that $$|S| < C_o (G’, S)$$, where we use $$C_o (G, S)$$ to denote the number of odd components of the graph $$G-S$$.

Note that the parity $$| S |$$ and $$C_o (G ’, S)$$ is the same because $$G$$ has an even number of vertices. Therefore, the inequality can be strengthened to $$| S | \le C_o (G ’, S) -2$$.

Therefore, for the number of edges $$\#e$$ leading to $$S$$ in the graph $$G$$ it holds that: $$\#e \le 3|S| \le 3 C_o(G’,S)-6.$$

If one of the edges connects vertices inside one component or inside $$S$$, then we derive the contradiction similarly as in the task with one prescribed edge. Therefore, we suppose that both edges connect odd components. We distinguish three cases:

• The edges $$e, f$$ connect two odd components into one even one. From this even lead at least two edges to $$S$$. Then $$C_o (G, S) = C_o (G’, S) -2$$ and $$\#e \ge 3 C_o(G,S) +2$$, together: $3 C_o(G,S) +2 \le \#e \le 3|S| \le 3 C_o(G’,S)-6 = 3 C_o(G,S).$
• The edges $$e, f$$ connect three odd components into one odd. From this odd component leads at least 5 edges to $$S$$. Then $$C_o(G,S)=C_o(G’,S)-2$$ and $$\#e \ge 3 C_o(G,S) +2$$, which leads to an inequality on the wall as in the previous case.
• The edges $$e, f$$ connect four odd components into two even ones. From these even components leads at least 8 edges to $$S$$. Then $$C_o(G,S)=C_o(G’,S)-4$$ and $$\#e \ge 3 C_o(G,S) +8$$, together: $3 C_o(G,S) +8 \le \#e \le 3|S| \le 3 C_o(G’,S)-6 = 3 C_o(G,S) +6.$