# Cubic graphs without a perfect matching and a vertex incident to three bridges

The example shown below (courtesy of David Eppstein) is a common example of a cubic graph that admits no perfect matching:

Are there other examples of cubic graphs that do not admit a perfect matching and, unlike the above example, do not contain a vertex that lies at the intersection of three bridges (i.e. an edge whose removal increases the number of connected components in the graph)?

-

Substitute your central vertex in your graph with a 3-cycle $abc$ so that the graph stays cubic. Now subdivide each edge in this 3-cycle. So we have new vertices $u$ connected to $a$ and $b$, $v$ connected to $b$ and $c$, $w$ connected to $c$ and $a$. Now add a final vertex $x$ and connect it to $u,v$ and $w$. This graph has exactly three bridges, none of which intersect the other at a vertex, and moreover has no perfect matching!

One result which relates the existence of a perfect matching in a cubic graph and its bridges is the following theorem of Petersen from "Die theorie der regularen graphen", Acta Math. 15 (1891), 163-220:

Theorem: Every cubic graph with at most two bridges contains a perfect matching.

As well as this strengthening by Errera, "Du colorage des cartes", Mathesis 36 (1922), 56-60:

Theorem: If all the bridges of a connected cubic graph $G$ lie on a single path of $G$, then $G$ has a perfect matching.

So your instinct is true, in the sense that if the graph has no perfect matching, its bridges do not lie on a path. However the example in the beginning of this answer shows that they are not necessarily incident at the same vertex.

-
Any two bridges lie on a path, so the second theorem is a strengthening of the first, not a converse. –  Brendan McKay Jun 1 '12 at 3:53
Oops! It's fixed. –  Gjergji Zaimi Jun 1 '12 at 5:02