0
$\begingroup$

I am given a graph $T$ with an odd number greater than or equal to 3 of vertices. Its line graph $L(T)$ has exactly one perfect matching.

I need to prove that if we remove any vertex from $T$, the number of even connected components in $T$ will be even.

I need an idea on how to start on this. How exactly does existence of the perfect matching in $L(T)$ influence the original graph?

$\endgroup$
2
$\begingroup$

This is not true. Consider $T=3P_3$. It has an odd number (9) of vertices.

The line graph $L(T)=3P_2$, which has exactly one perfect matching.

Nevertheless, if you remove an endpoint $v$ from one of the paths in $T$ you are left with $T-v$ which has an odd number (1) of even components.

It is also not true if $T$ is connected. Consider the claw $K_{1,3}$ and subdivide each edge. Verify that it has an odd number of vertices and that its line graph has a unique perfect matching. Now if you remove the central vertex you are left with three components of size $2$.

Note: you can in fact prove that in this case, the number of even connected components after vertex removal is always odd. Maybe that was the intention of the question?

$\endgroup$
  • $\begingroup$ Sorry, does the statement hold if the graph is connected? $\endgroup$ – mathpadawan Dec 16 '18 at 16:35
  • 1
    $\begingroup$ @mathnoob: I edited the answer to incorporate the reply to your question. $\endgroup$ – Leen Droogendijk Dec 18 '18 at 10:01

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.