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}