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