Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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. – Paul Z Aug 20 '12 at 16:20
Related question: – Douglas S. Stones Dec 27 '12 at 4:29

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.