22
$\begingroup$

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


(source: uci.edu)

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

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
23
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Any two bridges lie on a path, so the second theorem is a strengthening of the first, not a converse. $\endgroup$
    – Brendan McKay
    Commented Jun 1, 2012 at 3:53
  • $\begingroup$ Oops! It's fixed. $\endgroup$
    – Gjergji Zaimi
    Commented Jun 1, 2012 at 5:02
  • $\begingroup$ Why is it not enough just to substitute a 3-cycle for the central vertex? EDIT: Oh, I see, it has a perfect matching. $\endgroup$
    – Akiva Weinberger
    Commented Aug 12 at 20:07
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ @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. $\endgroup$
    – Gjergji Zaimi
    Commented May 30, 2012 at 15:30
  • $\begingroup$ 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? $\endgroup$
    – Anthony Labarre
    Commented May 30, 2012 at 15:32
  • $\begingroup$ @Anthony, pick your favourite cubic graph and substitute each vertex with a triangle. You get a claw free cubic graph. $\endgroup$
    – Gjergji Zaimi
    Commented May 30, 2012 at 15:33
  • $\begingroup$ @Gjergji Zaimi: Oh, right, I had overlooked the induced subgraph part ;-) Thanks! $\endgroup$
    – Anthony Labarre
    Commented May 30, 2012 at 15:38
  • $\begingroup$ Sorry for the wrong answer... $\endgroup$
    – Felix Goldberg
    Commented Jun 1, 2012 at 10:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .