# 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

I think there are no such graphs.

It was shown by Sumner and Las Vergnas (you can find the references here: http://mathsci.kaist.ac.kr/~sangil/pdf/2009claw.pdf) that a claw-free connected graph has a perfect matching (assuming even number of vertices, of course!). An intersection of three bridges is clearly a claw.

-
@Felix: What you are saying is that: no perfect matching implies there is a claw. But a claw does not necessarily imply three bridges. So this does not address the question. –  Gjergji Zaimi May 30 '12 at 15:30
This is surely simple, but given that every vertex in a cubic graph has by definition three neighbours, how can any cubic graph be claw-free? –  Anthony Labarre May 30 '12 at 15:32
@Anthony, pick your favourite cubic graph and substitute each vertex with a triangle. You get a claw free cubic graph. –  Gjergji Zaimi May 30 '12 at 15:33
@Gjergji Zaimi: Oh, right, I had overlooked the induced subgraph part ;-) Thanks! –  Anthony Labarre May 30 '12 at 15:38
Sorry for the wrong answer... –  Felix Goldberg Jun 1 '12 at 10:20