Lesson 4

Lemma. The graph \(G^{\star}-U\) is a disjoint union of complete graphs.

Proof. Suppose this is not true. Then in one connected component of \(G^{\star}-U\) there are vertices \(x,y,z\) such that \(xy,yz \in E(G^{\star})\), but \(xz \notin E(G^{\star})\).

Since \(y \notin U\), there is a vertex \(w \ne y\) such that \(yw \notin E(G^{\star})\). Notice that \(w \notin U\) as well. By maximality of \(G^{\star}\), the graphs \(G^{\star}+xz\) and \(G^{\star}+yw\) both have perfect matchings. Denote them by \(M_{1}\) and \(M_{2}\). Since \(G^{\star}\) itself has no perfect matching, \(xz \in M_{1}\) and \(yw \in M_{2}\).

Consider the graph with edge set \(M_{1} \triangle M_{2}\). It is a disjoint union of even cycles in which edges of \(M_{1}\) and \(M_{2}\) alternate. The edges \(xz\) and \(yw\) belong to exactly one of the two matchings, so they lie in this symmetric difference.

If \(xz\) and \(yw\) lie in different connected components of \(M_{1} \triangle M_{2}\), then we swap the matching on the cycle containing \(xz\). Starting from \(M_{1}\), this gives another perfect matching, but now it uses neither \(xz\) nor \(yw\). Hence it is a perfect matching of \(G^{\star}\), a contradiction.

Hence \(xz\) and \(yw\) lie in the same alternating cycle \(C\). By symmetry between \(x\) and \(z\), we may assume that the vertices appear on \(C\) in the cyclic order \(y,w,z,x\). Take the arc of \(C\) from \(x\) to \(y\) that avoids \(z,w\), then the edge \(yz\), and then the arc of \(C\) from \(z\) to \(w\) that avoids \(x,y\). This is a path \(P\) on the same vertex set as \(C\), it has an even number of vertices, and all its edges belong to \(G^{\star}\).

Therefore the vertices of \(C\) have a perfect matching using only edges of \(G^{\star}\): just take every other edge of the path \(P\). On every other alternating cycle, take either of the two alternating matchings, and keep all edges common to \(M_{1}\) and \(M_{2}\). Altogether this gives a perfect matching of \(G^{\star}\), a contradiction.

Therefore no such triple \(x,y,z\) exists, and every connected component of \(G^{\star}-U\) is complete.◼