1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Please use MathJax to format your posts. You'll get a much better response if your questions are easy to read. $\endgroup$
    – saulspatz
    Oct 31, 2020 at 20:39
  • $\begingroup$ 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 $\endgroup$
    – pasha
    Oct 31, 2020 at 20:58
  • $\begingroup$ @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. $\endgroup$ Oct 31, 2020 at 21:26

1 Answer 1

-3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Why is k lesser than j and not the other way round? $\endgroup$
    – pasha
    Nov 6, 2020 at 11:41
  • $\begingroup$ I don't understand your comment. We show precisely that $j$ is at most $k$. $\endgroup$
    – Max
    Nov 8, 2020 at 18:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .