I am trying to solve the following problem:

Let $G = (V,E)$ be a connected graph with an even number of edges. Show that $L(G)$, the line graph of $G$, has a perfect matching.

My approach is the following: Since the graph has even number of edges its line graph has even number of vertices. Also since the original graph is connected its line graph is connected as well. Therefore the problem can be translated as follows:

Prove that a connected graph with even number of vertices has a perfect matching.

I am a bit stuck on how to prove this though. I have tried to prove Tutte's Theorem but this didn't help me at all since I have no information for the odd components of the graph. Also I have tried to prove by contradiction that I can extend a maximal matching in the graph (if it doesn't have a perfect matching) but I don't have any information about the minimum degree of a graph. Finally I was thinking if I could use the fact that the graph has a spanning tree since it's connected but also I couldn't get up to something.

Can anyone provide some hint/direction so I can make some progress?


HINT: If you cut a set $S_E$ of $k$ edges from a connected graph $G$ w an even number of edges, then $G \setminus S_E$ has at most $k+1$ components [make sure you see why]. If $k$ is odd, then $G \setminus S_E$ has an odd number of edges, so as $k+1$ is even if $k$ is odd, at most $k$ of the components of $G \setminus S_E$ can have an odd number of edges. Likewise if $k$ is even, at most $k$ of the components of $G \setminus S_E$ can have an odd number of edges.

Use this to observe that removing a set of $k$ vertices from the line graph of $G$, will result in a graph $L'$ such that at most $k$ of the connected components of $L'$ have an odd number of vertices. Then finish with Tutte.

Meanwhile not every connected graph w an even number of vertices has a perfect matching, indeed consider the star graph w 4 vertices.

  • 1
    $\begingroup$ Thanks for the answer! Can I ask what gave you the idea of having this line of thinking? $\endgroup$ – koygian Aug 20 '18 at 16:55

In other words, you want to express the original $G$ as an edge-disjoint union of copies of $P_3$.

If the graph is a tree, choose a node to make it a rooted tree and pick a leaf with the maximal distance from the root. If this leaf has a sibling, then remove the path between the two sibling nodes. If it is an only child, remove the path between it and its grandparent. In either case you now have a tree with two nodes and two edges fewer. Proceed by induction.

If it is not a tree, it has a cycle. Choose an edge in the cycle, and detach it from one of its ends, introducing a new node of degree 1 instead. Keep doing this until there are $|E|-1$ nodes, at which point the graph has become a tree. Match up its edges as above.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.