# Cubic graph containing a 1-factor

• Robb

#### Robb

Homework Statement
Does there exist a cubic graph with three bridges that contains a 1-factor?
Relevant Equations
##k_0 (G-S) \leq |S|##

##k_0 (G-S) \leq |S|
I understand how to show a given graph does/does not contain a 1-factor but I'm not sure how to show existence (or the lack thereof). Please advise.

Please define 'factor' here. I am familiar with the concept of Bridges but not with the concept of factors. And maybe you can add tags at the end of your expression so the Latex can render?

1-factor is the same as a perfect matching-A graph G has a perfect matching iff for ##S \in V(G), k_o(G-S) \leq |S|##. If G has odd order, then G has no 1-factor. A 1-factor is a 1-regular sub-graph of G.
Also, every bridgeless cubic graph contains a 1-factor as well as every cubic graph with at most two bridges contains a 1-factor.

• WWGD
Restrict attention to a connected graph. If you remove the bridges the graph will fall into a number of components. What can you say about the number of vertices in each?

Since the thread seems to have died, here's my solution.