Graph with three bridges not in single path whith perfect matching

discrete mathematicsgraph theorymatching-theory

I want to show that it is possible to have a cubic graph $G$ with the following two properties:

  1. $G$ has three bridges that do not lie on a single path.
  2. $G$ has a perfect matching.

My attempts have been modifying the following graph

graph

(Image source: https://mathoverflow.net/questions/98385/cubic-graphs-without-a-perfect-matching-and-a-vertex-incident-to-three-bridges)

I have tried to replace the vertex $1$ with a graph such that it allowed to include all the edges adjacent to $1$ but all of my attempts have been unsuccessful.

Best Answer

enter image description here Please forgive the MS paint. This graph is clearly cubic and has a perfect matching. Notice also that there is no path that can cross all three bridges at once.

Related Question