Let $G$ be a loopless graph such that the degree of every vertex is even . Show that the line graph $L(G)$ of $G$ contains a matching of size at least $\frac{|E(G)|}{3}$.
My attaimpt: By a theorem due to Tutte and Berge, a graph $G$ has a matching of size $k$ iff for all $S\subset V(G)$, $Comp_o(G/S) \leq |S|+|V(G)|-2k$. Here $Comp_o(G)$ is the number of components with odd number of vertices(odd components) that is created after removing $S$ from $V(G)$.
The vertices in the line graph corresponds to the edges in the original graph. Also, the number of odd components that is created in $G$ after removing some edges is the number of odd components in $L(G)$ after removing the corresponding vertices in $L(G)$. So that means we need to show that for all $S \subset E(G))$, $Comp_o(G/S) \leq |S|+|E(G)|-\frac{2|E(G)|}{3}$. So I think each edge in $G$ can be connected to an even number of components as degree of each vertex in $G$ is even(I'm not sure of it). The point is I'm trying to give a bound on the size of $Comp_o(G/S)$. Is this the correct approach to the problem?
Best Answer
Assume $G$ is connected; if not, apply the result to every connected component of $G$ and then combine the matchings we get in their line graphs.
Since every vertex of $G$ is even, $G$ has an Eulerian tour. Let $e_1, e_2, \dots, e_m$ be the edges of the Eulerian tour, in order. Then the pairs $(e_1, e_2), (e_3, e_4), \dots$ form a matching in $L(G)$ of size $\lfloor \frac m2 \rfloor \ge \frac m3$.