Collection of Maths Problems

Two edges omitted in cubic graph

Task number: 4049

• 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. \]