Couples Problems (Unions of Perfect Matchings)

Question

You are at a party with $n$ couples. You have been introduced to all the couples, remember all the attendants of the party who belong to couples, but you may not remember everything about which pairs are couples (we can exclude and your date from the $2n$ people in couples, if you brought one, as if you do not remember that, you have a bigger problem than this one). In any case, you have a set of possible couples according to your subjective remembering. These are edges attaching vertices that are attendants in couples. But, with the information available to you, not all graphs on these vertices are possible. The condition is that your graph must be a union of a non-zero number of perfect matchings of its $2n$ vertices. For example, a graph with no edges is not allowed because it has no perfect matchings. A path graph on more than two vertices is not allowed because there is a vertex $v$ with degree one connected to a vertex $w$ of degree two. $v$ must be matched with $w$ under any arrangement of couples you believe to be possible, but then the other edge out of $w$ cannot be used in a perfect matching. When every vertex of degree greater than one is connected only to such vertices, we still may have a problem. Consider a bipartite graph with on part the vertices $(0,a)$ and the other part vertices $(1,a)$ with $a$ ranging from one to five in both cases. Take all and only edges with vertices $(b,1)$ and $(b,2)$ for $b=0,1$. This cannot work because once we have chosen at most four edges for the vertices $(b,1)$ or $(b,2)$, we still must have at least two unmatched vertices. (Technical detail: if you are rational in the game-theoretic sense, then the actual matching should belong to your graph, but we'll either ignore this detail, or count over all possible actual matchings.) How many ways can you remember who's with who? Is there any nice description of these graphs?

Answer 1

Since admissible graphs are unions of perfect matchings, a poly-time way to test whether a graph is admissible is to check whether every edge is in a perfect matching – remove the vertices incident to the edge being tested, then check whether the remainder has a perfect matching. In my view this is a sufficient characterisation.