# Extend Petersen's Theorem

This was a homework problem.

Petersen's Theorem: Every cubic, bridgeless graph contains a perfect matching.

Show that Petersen’s theorem (Theorem 8.11) can be extended somewhat by proving that if $$G$$ is a bridgeless graph, every vertex of which has degree $$3$$ or $$5$$ and such that $$G$$ has at most two vertices of degree $$5$$, then $$G$$ has a $$1$$-factor.

My idea was about splitting into $$3$$ cases, $$0$$ $$5$$-degree vertices, $$1$$ $$5$$-degree vertice and $$2$$ $$5$$-degree vertices. With $$0$$, it's obvious, but I can't figure out $$1$$ and $$2$$.

This is what I've done.

Case 1: $$G$$ has $$0$$ vertices of degree $$5$$. Automatically proven by using thm 8.11 (every $$3$$-regular bridgeless graph contains a $$1$$-factor)

Case 2: $$G$$ has $$1$$ vertice of degree $$5$$ Consider $$S$$ is a subset of $$V(G)$$

Let $$|S| = k$$ and $$|Ko(G - s)| = j$$. ($$Ko$$ being the number of components of a graph)

$$3 (k-1) + 5 \ge 3j$$ or $$3 (k-1) + 5 \ge 3(j-1) + 5$$

$$3 (k-1) + 5 \ge 3j \implies 3k - 3 + 5 \ge 3j \implies 3k + 2 \ge 3j \implies k + ⅔ \ge j$$

or $$3 (k-1) + 5 \ge 3j-3+5 \implies 3 k \ge j$$

Case 3: G has 2 vertices of degree 5

$$3 (k-2) + 5(2) \ge 3j \implies 3k - 6 + 10 \ge 3j \implies 3k + 4 \ge 3j \implies k + 4/3 \ge j$$

or $$3(k-2) + 5(2) \ge 3(j-1)+5 \implies 3k+4 \ge 3j+2 \implies 3k+2 \ge 3j$$

or $$3(k-2) + 5(2) \ge 3(j-2)+10 \implies 3k+4 \ge 3j+4 \implies k \ge j$$

Where do I go from here? Is my setup completely wrong?

• Please use MathJax to format your posts. You'll get a much better response if your questions are easy to read. Oct 31, 2020 at 20:39
• In the post the spelling is correct. I added the theorem statement as you suggested, but it's not like I was talking about a textbook specific thing. Petersen's Theorem is a theorem by itself. Also are there any MathJax permissions I need to set? I replaced >= with \ge but it showed as text instead of the symbol. I also tried 3^3 as a test, and that also showed as raw text Oct 31, 2020 at 20:58
• @pasha FYI, a good MathJax tutorial, that I quite often use myself, is MathJax basic tutorial and quick reference. As for your specific question, I believe the issue is you need to use $ both before and after the MathJax text for it to be interpreted as such when it's inline text. Oct 31, 2020 at 21:26 ## 1 Answer There are some typos/mistakes in the inequalities in the cases $$1$$ and $$2$$. After they are fixed you get in case $$1$$ that $$k\geq j+2/3$$. However since they are both integers, $$k\geq j$$, which is what you need to apply Tutte's theorem. In case $$2$$ you only get $$k\geq j+4/3$$, which means that either $$k\geq j$$ (which is good), or, potentially, that $$k=j-1$$, which would be bad. However, this is actually not possible: either there is at least one edge between the vertices if $$S$$ or there isn't. If there is then $$3(k−2)+5(2)-2\geq 3j$$ and we are back to $$k\geq j+2/3$$. But if there isn't then all $$3k+4$$ edges go out to $$j=k+1$$ components, with all of them getting odd number and at least 3 each - which is is not possible (you can check why). So in all cases $$k\geq j$$ and you can apply Tutte's theorem. • Why is k lesser than j and not the other way round? Nov 6, 2020 at 11:41 • I don't understand your comment. We show precisely that$j$is at most$k\$.
– Max
Nov 8, 2020 at 18:50