Graph with bridge and perfect matching.

619 Views Asked by At

I am asked to prove to construct two $3$-regular graphs $G, H$ that contain at least one bridge with the following properties: $G$ should contain a perfect matching, which you will illustrate; $H$ should not contain a perfect matching and you should justify why.

I have find a graph $G$ but anyone can explain if I can find a graph $G$, how can I prove graph $H$ which hasn't contain a perfect matching

Thanks

2

There are 2 best solutions below

0
On

Graph $G$, red edges are from perfect matching.enter image description here

0
On

Hint: suppose

enter image description here

has a perfect matching, including the horizontal edge extending to the left.

Then one of these has a perfect matching, but the other does not.

enter image description here

enter image description here