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?
Best Answer
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.