Let there be $G$ an $r$-connected simple graph for $r \geq 1$ with an even number of vertices, we also know that $K_{1,r+1}$ is not a subgraph of $G$, I need to show that $G$ contains a perfect matching.

My initial approach was attempting to use a similiar method to the proof of Tutte's theorem then for any set of vertices less than $r$ the condition holds trivially. For a subset of vertices $S$ s.t. $|S|>r$ I wanted to somehow show that if $o(G\setminus S)>|S|$ then there has to be a $K_{1,r+1}$ subgraph.

  • $o(G\setminus S)$ in this context means the number of odd connectivity components of $G\setminus S$
  • $K_{1,r+1}$ is the $r+1$ edges star graph.

Would appreciate some hints.

  • $\begingroup$ Really, an "$r$ minus $c$ times $o$ times $n$ times $n$ times $e$ times $c$ times $t$ times $e$ times $d$" graph? Or did you mean an "$r$-connected" graph? (But seriously, math mode is for math. Use *italics* to make italics.) $\endgroup$ – Zev Chonoles Feb 13 '14 at 5:56

Since $G$ has no $K_{1,r+1}$ then the degree $d(v) \le r$ for any vertex v. Also, since $G$ is $r$-connected, then $G$ is at least $r$-edge-connected graph and $d(v) \ge r$ for any vertex v. Hence, $G$ is $r$-regular $r$-edge-connected graph.

For $S \subset V(G)$, let $G_1, G_2, \cdots G_k$ be the odd components of $G \setminus S$.Let $m_i$ be the number of edges between $G_i$ and $S$.By edge connectivity of $G$, we have $m_i \ge r$ which means $\frac{m_i}{r} \ge 1$.

Notice that $\sum_{i=1}^{k}m_i \le r|S|$ i.e. the total number of edges between the $G_i$ and $S$ is less than the total number of edges that could possibly come from $S$ ( $r|S|$ since $G$ is $r$-regular.)

In an other word, $|S| \ge \frac{1}{r}\sum_{i=1}^{k}m_i = \sum_{i=1}^{k}\frac{m_i}{r} \ge k = o(G \setminus S)$, thus by Tutte's theorem $G$ has a perfect matching.

  • $\begingroup$ as per your answer doesn't that mean the number of components are less than or equal to |S|? Where have you used that G_i 's are odd components ? $\endgroup$ – Jagdeep Singh Feb 20 '17 at 14:07

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.