Perfect matching in a line graph

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

I was thinking of doing the same proof as hmakholm did. Instead of dividing into two cases (tree, not tree), the following also works.

Consider a rooted spanning tree $T$ of $G$. Pick a leaf $v$ in the lowest level of $T$. Let $e_1$ be the edge incident to $v$ in $T$. If $d_G(v)$ is even, we keep removing pairs of edges incident to $v$ in $G$ until $v$ is isolated. Otherwise, remove pairs of edges as many as possible, without touching $e_1$. There is only $e_1$ left. Do the same thing for the siblings of $v_1$. If there are odd many siblings, each has one edge left, pair $e_1$ and the remaining edges of siblings. If $v$ is the only child, or there are even number of siblings, pair the edges of siblings, pair $e_1$ with the edge between the parent and grandparent of $v$. Then, remove isolated vertices. The remaining graph is connected, because the remaining $T$ is connected. Repeat the same process on $G$ picking a spanning tree of it.