Collection of Maths Problems

k-regular edge (k-2)-connected graph

Task number: 4053

• Hint

  Construct an odd component and a set \( S \) so that it can be seen that the resulting graph violates Tutte’s condition.

• Solution

  For even \( k \) we create an odd component from \( K_{k + 1} \) so that we select a matching on \( \frac{k-2}{2} \) edges, and remove those edges. Let’s call this graph \( K’\).

  We take a total of \( k \) copies of \( K’\) and add to them \( k-2 \) new vertices forming the set \( S \). We connect these parts so that each vertex of \( S \) is adjacent to one vertex from each copy of \( K’\) and that the resulting graph is \( k \)-regular. In other words, the edges between \( S \) an4d each copy of \( K’\) form a perfect matching between \( S \) and the vertices of degree \( k-1 \) in \( K’\).

  After removing the set \( S \) from the resulting graph \( G \) we have \( | S + 2 | \) odd components, and therefore \( G \) violates Tutte condition and does not have a perfect matching.

  It remains to show that if we remove any \( k-3 \) edges from \( G \), the graph will remain connected. Each copy of \( K’\) will have a vertex adjacent to the others, so it is connnected. From each vertex \( S \) at least one edge leads to some copy of \( K’\). According to Dirichlet’s principle, at least one vertex of \( S \) is adjacent to all copies of \( K’\), so the resulting graph is connected.

  For odd \( k \) we proceed in the same way, only the construction of \( K’\) requires one extra step. As in the previous case we select from \( K_{k + 1} \) a matching on \( \frac{k-3}{2} \) edges, and remove those edges. Next, we choose another matching with \( \frac{k-1}{2} \) edges. We subdivide each edge of this matching with one new one vertex. We merge these \( \frac{k-1}{2} \) vertices into one, and obtain the \( (k-2) \)-nd, i.e. the last required vertex of degree \( k-1 \).

  It remains to verify that the resulting graph \( K’\) is sufficiently conneceted. By using Menger’s theorems, it can be shown that the addition of a single vertex, which results from the merge of vertices of subdivided edges, maintains the \( (k-2) \)-connnectedness.