Tutte's theorem as stated on wikipedia says:

A graph, $G = (V, E)$, has a perfect matching if and only if for every subset $U$ of $V$, the subgraph induced by $V − U$ has at most $|U|$ connected components with an odd number of vertices.

Is the graph $G$ assumed to be simple? If not, why does Andersen's proof of Tutte's theorem here begin by considering only simple graphs?

  • $\begingroup$ A graph with multiple edges has a perfect matching if and only if the underlying simple graph has a perefect matching. $\endgroup$ – Chris Godsil Feb 17 '16 at 5:19

The statement of Tutte's theorem does not really mention edges. So suppose there are possibly loops and multiple edges between vertices. Then $V-U$ has exactly the same number of connected components as the graph you'd get by removing the extra edges and loops because deleting a vertex from a graph removes all the edges and loops do not do anything for connectivity.

This of course, is assuming that whatever notion of matching we are using for a multigraph does not allow loops as part of the matching, for otherwise we could take the standard example of a 3-regular graph without a perfect matching and add one loop to every vertex to obtain a perfect "matching" consisting of just the loops.

enter image description here

  • $\begingroup$ What about we change the statement (which I feel is really about certificates) to a component is odd if it is odd and has no loop $\endgroup$ – Hao S Nov 25 '19 at 20:10
  • $\begingroup$ You will have to make a new question defining the terms certificate, component and what it means for a component to be odd. $\endgroup$ – RKD Nov 26 '19 at 22:50
  • $\begingroup$ @RDK math.stackexchange.com/questions/3450838/… Also I stated a component is odd if it is odd and has no loop. So one can ask if the maximum number of vertices in a matching of a graph with loops (where a loop means a vertex can be matched with itself ) is k less than the number of vertices then does there necessarily exist a set of vertices A such that G \ A has k + |A| odd components? $\endgroup$ – Hao S Nov 27 '19 at 23:33

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.