1-factorization: Possible that a graph G has a 1-factorization, but there is a 1-factor F so that G-F has no 1-factorization

73 Views Asked by At

I'm struggling with imagining a graph $G$ that has a 1-factorization, but there is a 1-factor $F$ so that $G-F$ has no 1-factorization.

I can properly prove that the Petersen-graph has no 1-factorization. But I am not confident in a different approach. So it is easy to find a 1-factor of the Petersen-graph by matching the inner vertices to the outer vertices. Then there are two circles left with five vertices each, so obviously there cannot be another 1-factor remaining. But does that prove that Petersen-Graph has no 1-factorization? Because one could argue that if we started with a different 1-factor and then reduced the graph, we could have found another (or two) 1-factors.

Then I tried to construct a graph that has a 1-factorization, which I can reduce to a graph that has no more 1-factorization, but I failed for now. There is for example the complete bipartite graph $K_{3,3}$. This one has as far as I can see four different 1-factors and for a 1-factorization I only need three of them. But reducing the graph by any of the 1-factors I can still factorize the graph.