Does Tutte's theorem apply for simple graphs only
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?
$\endgroup$ 11 Answer
$\begingroup$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.
