3
$\begingroup$

There is a fairly rich classification on graphs with respect to the existence of Hamiltonian cycles either in unmodified graphs or after certain small modifications.

Do there also exist such classifications with respect to perfect matchings? Specifically, I would like to know, whether there exist

  • "Hypo-Matching" graphs that do not contain a perfect matching, but removing an arbitrary pair of vertices generates a graph with perfect matching.

  • "Hyper-Matching" graphs with a perfect matching, for which removing an arbitrary pair of vertices generates a graph with perfect matching.

$\endgroup$
3
  • $\begingroup$ could the downvoters please indicate their motivation (I can't see why the question is inappropriate for MO)? $\endgroup$ Dec 20 '15 at 16:28
  • $\begingroup$ should the second "with" in the second bullet point be "without"? $\endgroup$ Dec 20 '15 at 19:02
  • 1
    $\begingroup$ I think "with" is correct since my understanding is that hyper-Hamiltonian graphs should be Hamiltonian to start with and remain Hamiltonian after removing a vertex. $\endgroup$ Dec 20 '15 at 19:36
4
$\begingroup$

A hypo-matching graph cannot exist. Assume $G$ does not contain a perfect matching, but $G - \{u,v\}$ does. This means $uv$ is not an edge is $G$ or else $G$ has a perfect matching. This cannot hold for an arbitrary pair of vertices since that would force $G$ to be edgeless.

A hyper-matching graph definitely exists. Just consider the complete graph on $2n$ vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.