Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$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?

Thanks.

share|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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.