Matchings · Theory Problems

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Optional Problems.

Tutte's Theorem and Berge's Formula.

  1. (20 points) A graph \(G\) is called factor-critical if for every vertex \(u\in V(G)\) the graph \(G-u\) has a perfect matching. A matching in \(G\) is called near-perfect if it covers all vertices of \(G\) except one. Recall that \[\operatorname{def}(G)=|V(G)|-2\alpha'(G).\] Prove that if \(G\) is a connected graph such that \[\alpha'(G-u)=\alpha'(G)\] for every vertex \(u\in V(G)\), then \(G\) is factor-critical.
  2. (30 points)
    • (20 points) Prove that every connected \(3\)-regular graph with at most two bridges has a perfect matching.

    • (10 points) Show also that the bound on the number of bridges is best possible: construct a connected \(3\)-regular graph with three bridges and no perfect matching.

  3. (30 points) Let \(G\) be a \(k\)-regular graph with an even number of vertices and edge-connectivity \(\lambda(G)\ge k-1\). Let \(G'\) be obtained from \(G\) by deleting at most \(k-1\) edges. Prove that \(G'\) has a perfect matching.