I'm preparing for an exam and I am not sure if my solution to a particular question is viable. Maybe somone can shed some insight?

The question: Given an $r$-connected graph $G$ on an even number of vertices such that there is no $K(1,r+1)$ (That is the complete, two sided graph with sides of size 1 and $r+1$). Prove that $G$ has a perfect mathing.

Attempted solution: First, by Mengers theorem for any two vertices, $u$ and $v$, there are at least $r$ vertices distinct paths between them. Also, the minimal degree of any vertex is at least $r$. We proceed by double induction, the first on r and the second on the number of edges. Base for first induction: $r=1$ then there is only one graph that satisfies the property and that is the complete graph on two vertices. Thus we assume for $r-1$ and prove for $r$.

Next We proceed with the induction on the number of edges. Base: A graph with minimal degree $r$ has at least $r+1$ vertices so the minimal number of edges is $r^2+r$. That is, our base case is the complete graph on $r+1$ vertices. We are given that $r+1$ is even and an even complete graph has a perfect matching.

Step: Now we assume for any graph with the above properties and $k$ edges and prove for a graph with $k+1$ edges. and such graph has at least $r+2$ vertices,and since it contains no $K(1,r+1)$ there exist vertices $u$ and $v$ with no edge between them. Removing any edge from $u$ we have a graph that is at worst $r-1$ connected with $k$ edges. Applying the second inductive hypothesis and possibly the first, we a have a perfect matching as required. Thats it, I hope. What do you think? Thanks!

  • $\begingroup$ I am suspicious because your first proof doesn't say anything about non-complete graphs, yet you seem to be hoping for such a result in the second part of the proof. It may be worth considering the fact that every node in the graph always has exactly $r$ edges. $\endgroup$
    – Paul Z
    Aug 20, 2012 at 16:20
  • $\begingroup$ Related question: math.stackexchange.com/questions/183355 $\endgroup$ Dec 27, 2012 at 4:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.