1
$\begingroup$

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$
1
  • $\begingroup$ A graph with multiple edges has a perfect matching if and only if the underlying simple graph has a perefect matching. $\endgroup$ Commented Feb 17, 2016 at 5:19

1 Answer 1

4
$\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.

enter image description here

$\endgroup$
3
  • $\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
    Commented Nov 25, 2019 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$
    – Arkady
    Commented Nov 26, 2019 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
    Commented Nov 27, 2019 at 23:33

You must log in to answer this question.