G0 have degree ≥ 3. By Lemma 3. 3, graph G0 again has small cycles of length ≤ 4 log n. Now, we can repeat the procedure of eliminating all cycles of length ≤ 4 log n with G0.

In every round, the number of nodes in the graph decreases by a constant fraction. Thus, in O(log n) rounds, we eliminate all cycles and reach the empty graph. One can easily obtain a unique perfect matching in the original graph G, by reversing all the degree- 1 deletions and degree- 2 collapses.

3. 3. Approach 3: Eliminating a maximum size set of
edge-disjoint cycles

In this approach, we do not consider the lengths of the cycles. Instead, in each round we pick as many edge-disjoint cycles as possible. Recall that eliminating a cycle means that at least one of its edges will not be present in the graph in the next round. Hence, when we eliminate a set of edge-disjoint cycles, we will eliminate at least as many edges. Once we remove enough edges, we will be left with no cycles.

Let G be a graph with n vertices and m edges. The number of cycles picked in each round is trivially bounded by m. The non-trivial part is to come up with a lower bound. Erdös and Pósa9 showed that G has at least edge-disjoint cycles. We will argue that if we eliminate a maximum size set of edge-disjoint cycles in a round, then the quantity m − n decreases by a significant fraction in every round.

Lemma 3. 4. Let G be a connected graph with n vertices and m edges. Let C be a maximum size set of edge-disjoint cycles in G. Let H be any subgraph of G obtained by deleting at least one edge from each cycle in C. Then for any connected component H1 of H with n1 vertices and m1 edges,

Proof. Let |C| = k. Let H′ be any subgraph of G such that H is a subgraph of H′ and for each cycle in C, exactly one edge is missing in H′. Note that H′ is still connected, since the cycles in C are edge-disjoint. The difference between the number of edges and vertices of H′ is m − n − k.

Since H is obtained by deleting possibly some more
edges from H′, for any connected component of H, the dif-
ference between the number of edges and vertices cannot
be larger than m − n − k. Now, the lemma follows from the
equal parts. We associate the tuple (u0, u1, u2, u3) with C. We
claim that C is the only cycle associated with (u0, u1, u2, u3).
For the sake of contradiction, let there be another such cycle
C′. Let p ≠ p′ be paths of C and C′, respectively, that connect
the same u-nodes. As the four segments of C and C′ are of
equal length, we have |p|, |p′| ≤ r/2. Thus, p and p′ create a
cycle of length ≤r, which is a contradiction. Hence, a tuple
is associated with only one cycle. The number of tuples of
four nodes is bounded by n4 and so is the number of cycles
of length ≤2r. 

3. 2. Approach 2: Eliminating small cycles implies a
small average degree

Here, the idea is to use a result of Alon, Hoory, and Linial, 2 which states that a graph with no small cycles must have many nodes of degree ≤ 2. To get an intuitive understanding of this, consider a graph where each node has degree at least 3: do a breadth-first search of the graph starting from an arbitrary node until depth log n. When one reaches a node v via an edge e, there are at least 2 edges incident on v other than e. So, the search tree contains a binary tree of depth log n. The nodes in the tree cannot be all distinct, because otherwise we would have strictly more than 2log n = n nodes. A node that appears twice in the search tree gives us a cycle of length at most 2 log n. In other words, if there are no cycles of length at most 2 log n, then the graph must have a node with degree 2 or less. Alon, Hoory, and Linial2 generalize this intuition to show that as the length of the shortest cycle increases, the average degree gets closer to 2.

Lemma 3. 3 (Alon, Hoory, and Linial). Let H be a graph with no cycles of length < 4 log n. Then H has average degree < 2. 5.

In this approach, we start by eliminating all cycles in graph G of length ≤ 4 log n. It is easy to see that the number of such cycles will be bounded by n4 log n. Lemma 3. 3 implies that after this, a constant fraction of the nodes in G have degree ≤ 2.

Having many nodes of degree ≤ 2 is quite useful when we are interested in perfect matchings because they provide a way to shrink the graph while preserving perfect matchings.

 

1. Let v be node of degree 1 in G and u be the unique neighbor of v. Recall that our graph after every round is always a union of perfect matchings. Therefore, u has degree 1 as well. Hence, we can simply delete u and v from G.

2. Let v be a node of degree 2 in G with its neighbors u and w. Now, construct a new graph G′ from G by deleting v and identifying u and w to get a single node {u, w} (see Figure 4). We refer to this operation as collapsing the node v. Observe that perfect matchings of G and G′ are in one-to-one correspondence.

 

Note also that any cycle in G appears in G′ with the degree- 2 nodes cut out, that is, cycles get shorter in G′.

To further proceed in this approach, we first collapse all degree- 2 nodes in G (one by one) and delete all degree- 1 nodes. Let G0 be the resulting graph. Since there were a constant fraction of nodes with degree ≤ 2 in G, the number of nodes in G0 decreases by a constant fraction. Note also that all nodes in

Figure 4. Deleting a degree- 2 node v and identifying its two neighbors u and w—an operation which preserves perfect matchings and cycles.

u v w

{u, w}