Cubic graph containing a 1-factor

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

 

[WWGD]

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?

 

[Robb]

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.

 

[haruspex]

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?

 

[haruspex]

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

Start with three pentagonal circuits and a triangle.
Connect each vertex of the triangle to a vertex of a pentagon to make the graph connected with three bridges.
Within each pentagon, connect the remaining four vertices as two pairs, making the graph cubic.