I have a connected, bridgeless graph with 72 vertices of degree 3 and 2 vertices of degree 2. Is there a way that I can prove that this graph has a perfect matching?
From the graph I can see there is a perfect matching, but I would like to obtain it by a proof without getting from the drawing. (Even by thinking of a general case, like a connected, bridgeless graph has k number of vertices of degree 3, where k is even and 2 vertices of degree 2. Then can we prove that it has a perfect matching?)
Please help me with this question.
Thanks a lot in advance.
Attached below is the mentioned graph. Please consider that the point marked as 52, enclosed in a square is not a part of the graph. Is there any suggestion to prove that this graph is bridgeless (if I do not know its bridgeless)?
If the two degree 2 vertices are not connected, connect them by an edge and apply Peterson's theorem and use the fact that you can pick any edge and there will be a perfect matching without that edge. Else, say the edge connecting them is $uv$, subdivide it and add a new vertex $S$ as in the following picture. So apply Peterson on the resulting graph with $SW$ removed!?