Is it possible to have a graph with a perfect matching, add 4 vertices and have a perfect matching for the bigger graph (+ one more condition)?

Question

I encountered this problem about perfect matchings in my project and it is actually pretty important for the progress. It would be great if someone here can give me an idea (or even a solution to it). Since I am not very familiar with graph theory, please feel free to let me know if the language I'm using to describe the problem is not clear.

Does a graph G=(V,E) exist which has these properties:

• it has at least one perfect matching
• one can add 4 vertices V' (and edges E' between V and V' or within V') in such a way that new graph G'=(V ∪ V' , E ∪ E') also has at least one perfect matching.
• a̶l̶l̶ ̶p̶e̶r̶f̶e̶c̶t̶ ̶m̶a̶t̶c̶h̶i̶n̶g̶s̶ ̶o̶f̶ ̶G̶ ̶a̶r̶e̶ ̶m̶a̶x̶i̶m̶a̶l̶ ̶m̶a̶t̶c̶h̶i̶n̶g̶s̶ ̶o̶f̶ ̶G̶'̶
• updated: all matchings of G' which match all of V match either no vertex in V' or all of V' (not a strict subset of V')

This would have the consequence that the vertices V' are special vertices that are either all included in the perfect matching of G' or all excluded from the perfect matchings of G with no way of including a strict subset in a matching that matches all vertices of the smaller graph.

I have shown for myself that the answer is 'no' for adding odd numbers of vertices (for parity reasons - a perfect matching needs an even number of vertices), but I really want to know if it's the same for four (which I could generalize to all even numbers).

I would be really excited if someone could help me.

Thank you!

Answer 1

So long as the vertices $V'$ that you add form an independent set (none are adjacent to eachother), you automatically get condition 3 (this is sufficient and necessary).

So take the 4-cycle $C_4$ on vertices $v_1, v_2, v_3, v_4$ as $G$. Add 4 vertices $V' = \{u_1, u_2, u_3, u_4\}$, and make u_i and v_i adjacent to get $G'$. This satisfies all 3 conditions.

I'm not sure what you mean by this paragraph:

This would have the consequence that the vertices V' are special vertices that are either all included in the perfect matching of G' or all excluded from the perfect matchings of G with no way of including a strict subset of them.

Surely a perfect matching of just $G$ never includes anything else? Or do you mean `any matching of $G'$ that contains a perfect matching of $G$' when you talk about the perfect matchings of $G$?

As a final note: there's nothing special about $C_4$. This construction (and many others where $V'$ is an independent set) works for any graph with an even number of vertices.