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

$G$ is a simple $r$-connected ($r \geq 1$) graph, with even number of vertices. Assume that $G$ doesn't contain $K_{1,r+1}$ as an induced subgraph. Prove that $G$ has a perfect matching.

Now, I can see why it's true without the condition on $K_{1,r+1}$: obviously, $\delta(G) \geq r$, and then, by using Tutte's theorem in a fashion of a proof of Petersen theorem ($ro(V[G-S]) \leq \sum{M_i} \leq \sum_{v \in S}d(v) \leq r|S|$, when $M_i$ is number of edges between $S$ and a component $C_i$), I'm getting to what I was needed to prove.

Am I missing something?


share|cite|improve this question
What happens when you try and run through your argument on $K_{r,r+2}$? – Kevin Costello Aug 16 '12 at 19:56
I'm not sure... What is the $S$ I need to take for the argument to fail? – Pavel Aug 17 '12 at 6:02
If you remove the $r$ vertices on the smaller side, you leave $r+2$ odd components. – Kevin Costello Aug 17 '12 at 8:51
Oh, right. So it's a precondition for not getting too many (odd) components. Seems like, though, in that case, it doesn't require any additional proof? – Pavel Aug 17 '12 at 9:57

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.