Matching in General Graphs¶

If edges \(ad\) and \(bc\) are in two different cycles¶

Then, from the cycle containing \(ad\), choose edges of \(M2\), and from the cycle containing \(bc\), choose edges of \(M1\) (from the remaining cycles, choose edges of \(M1\) or \(M2\) arbitrarily, and also choose edges that are in \(M1 \cap M2\)). In this case, we will have a perfect matching in \(H\)!

If edges \(ad\) and \(bc\) are in the same cycle¶

First, we must state that this cycle is even. Now, since \(bc\) is one of the edges of the cycle, \(b,c\) are two consecutive vertices in the cycle. Therefore, it happens that for exactly one of the edges \(ab\) or \(ac\), the following occurs:

If we remove the vertices at the ends of the edge, our cycle will turn into two even-vertex paths.

Without loss of generality, suppose this edge is \(ab\). Now, choose edge \(ab\) for the matching. Then, remove \(a,b\) from the graph and alternately choose edges from the two even-vertex paths formed for the matching. In this way, all vertices of our cycle will be covered by the selected edges. Similarly, from the remaining cycles, arbitrarily choose edges from \(M1\) or \(M2\), and also choose edges that are in \(M1 \cap M2\). In this case, we will have a perfect matching in \(H\)!

What if we don't have a pear?¶

In the two sections above, we proved that if graph \(H\) has a pear, then \(H\) contains a perfect matching. Now we must also consider cases where no pear exists in \(H\).

Consider the set \(C\) to include all vertices of \(H\) that have edges to all other vertices (their degree is \(n-1\)).

Now, if \(C\) includes all vertices of \(H\), this means that \(H\) is a clique (and has an even number of vertices). Thus, a perfect matching clearly exists in it.

So consider the graph \(W = H-C\). In \(W\), for every vertex like \(u\), there exists a vertex like \(v\) such that there is no edge between \(u\) and \(v\) (why?). Thus, if we can find an apple in \(W\), then we can also find a pear (because it is sufficient to find a vertex \(d\) for vertex \(a\) in the apple such that there is no edge between \(a\) and \(d\)).

So if an apple exists in \(W\), the problem is solved. Now, assume that no apple exists in \(W\). In this case, for any arbitrary \(a,b,c\) such that \(ab,ac\) are edges of the graph, \(bc\) must also be an edge of this graph. Consider an arbitrary vertex like \(u\), and let \(A\) be the set containing \(u\) itself and its neighbors. There must be an edge between any two vertices in \(A\) (why?). Also, no vertex outside \(A\) has an edge to \(A\) (why?). Therefore, it can be concluded that every connected component in \(W\) is a clique. Match vertices arbitrarily within each clique. Exactly one vertex remains unmatched from each odd-sized clique. Since Tutte's condition holds for \(S = C\), all remaining unmatched vertices in \(W\) can be matched to vertices in \(C\). Finally, we arbitrarily match all remaining unmatched vertices in \(C\) (which form an even-sized clique). Thus, we have found a perfect matching in \(H\).

A Wrong Idea¶

Probably the first idea that comes to mind is to copy vertex \(u\) exactly \(a_u\) times, then for each edge \(uv\) in \(G\), add an edge between all copies of \(u\) and \(v\). Then check if a perfect matching exists in the new graph.

This idea is very similar to what we discussed previously in the bipartite matching chapter, but it has a very subtle mistake. The problem is that we might simultaneously use several edges between \(u\) and \(v\) in the matching, and this causes us to use one edge multiple times, which is not desired by the problem.

The Correct Solution¶

Let \(d_u\) be the degree of vertex \(u\). We construct graph \(G^{\prime}\) from graph \(G\) as follows:

For each vertex \(u\), we place a complete bipartite graph! Such that its first part has \(d_u - a_u\) vertices, and its second part has \(d_u\) vertices. We call the bipartite graph corresponding to vertex \(u\), \(B_u\). Then, consider the edges of graph \(G\) in an arbitrary order and add their counterparts (as we will describe) to graph \(G^{\prime}\). Suppose the \(i\)-th edge we examine is \(uv\), and before it, we have examined \(c1\) edges incident to \(u\) and \(c2\) edges incident to \(v\). Now, the counterpart of edge \(uv\) will be an edge between the following two vertices:

• The \(c1\)-th vertex of the second part of graph \(B_u\)

• The \(c2\)-th vertex of the second part of graph \(B_v\)

Now we claim that the existence of a subset \(M\) of edges that satisfies the problem's condition is equivalent to the existence of a perfect matching in graph \(G^{\prime}\)!

Note that in this graph, each edge in the original graph has exactly one corresponding edge, so the previous problem (using an edge multiple times) does not arise. The complete proof of the correctness of the above theorem is left to the reader.