2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ What happens when you try and run through your argument on $K_{r,r+2}$? $\endgroup$ – Kevin P. Costello Aug 16 '12 at 19:56
  • $\begingroup$ I'm not sure... What is the $S$ I need to take for the argument to fail? $\endgroup$ – Pavel Aug 17 '12 at 6:02
  • $\begingroup$ If you remove the $r$ vertices on the smaller side, you leave $r+2$ odd components. $\endgroup$ – Kevin P. Costello Aug 17 '12 at 8:51
  • $\begingroup$ 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? $\endgroup$ – Pavel Aug 17 '12 at 9:57
1
$\begingroup$

Yes the mistake is that you'll need, for each odd component $C$ with neighbours $N'(C)$ in $S$, to allow counting at most one edge for a vertex in $N'(C)$ (i.e. you'll count a smaller set of edges such that no two vertices in the same component are sharing the same vertex in $S$) that's the only way to be able to make the last inequality.

And, in jumping to the last inequality you'll now need to use the special bipartite-free condition (this is a generalization of Petersen's theorem).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.