467 views
1 votes
1 votes
a tree with n vertices can have at most 1 perfect matching how?

 

 

perfect matching means no vertices will be left with 0 dergree right so how a tree can have a perfect matching

explain with the help of trees plz

1 Answer

0 votes
0 votes

We'll simply show that we don't have any choices to make, so that if there is a perfect matching, it's determined by the tree. Consider some leaf u. It must be matched with its parent, v. Vertex v might be adjacent to some other leaves, in which case there is no perfect matching. If not then remove the edge uv (since it must be in a perfect matching) and continue. We know that since the graph is acyclic, we'll always have a leaf. We continue the procedure until we end up with a perfect matching, or along the way find there isn't one. Since we never made any choices (every leaf must matched to its parent), there is at most one perfect matching.
perfect matching is matching with a covering . take set of those independent edges which would cover all the vertices here.

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
2
shuham kumar asked Nov 18, 2022
391 views
how many subgraph with atleast 1 vertex does k2 have? (graph theory question)
2 votes
2 votes
1 answer
3
jugnu1337 asked Dec 17, 2021
514 views
complete directed graph with 8 vertices has 28 edges this statement is true or falseplese explain?
5 votes
5 votes
2 answers
4
Nidhi Budhraja asked Aug 26, 2018
2,379 views
Stmt 1: A simple graph is necessarily connected if |E| (n-1)*(n-2)/2.Stmt2: A simple graph with n vertices and k components has at least n-k edges.Can you please explain...