Can Tutte's theorem be extended for infinite graphs? If so, what is the proof?

The theorem: 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

  • 5
    $\begingroup$ The concept of "odd number" is somewhat useless when it comes to infinity :-) $\endgroup$ – Peter Košinár Jul 16 '13 at 22:18

The following proof is from a note by W. H. Gottschalk (Proceedings of the American Mathematical Society, Vol. 2, No. 1 (Feb., 1951), p. 172). The theorem was first stated by R. Rado.

Theorem: Let $(X_\alpha:\alpha\in I)$ be a family of finite sets, let $\mathcal{A}$ be the collection of finite subsets of $I$ and for each $A\in\mathcal{A}$, let $\phi_A$ be a choice function for $(X_\alpha:\alpha\in A)$ (a choice function for the (finite) collection of subsets $(X_\alpha : \alpha\in A)$ is a function $\phi_A$ that associates to each $\alpha\in A$ an element $\phi_A(\alpha)$ of $X_\alpha$. Then there exists a choice function $\phi$ of the (infinite) collection $(X_\alpha:\alpha\in I)$ such that $A\in \mathcal A$ implies the existence of $B\in \mathcal A$ such that $A\subset B$ and $\phi(\alpha)=\phi_B(\alpha)$ for each $\alpha\in A$.

Before I explain why this theorem is useful, I'll show you Gottschalk's remarkable short proof.

Proof: Let $X$ be the set of all choice functions for $(X_\alpha:\alpha\in I)$. For each $A\in\mathcal A$, let $E_A$ be the set of all choice functions $\phi\in X$ such that $\phi(\alpha)=\phi_B(\alpha)$ ($\forall \alpha\in A$) for some finite $B\supset A$. So if we can prove that the collection $(E_A:A\in\mathcal A)$ has a non-empty itersection, then we win. We do this by giving each $X_\alpha$ the discrete topology. Then $X$ is a product of the $X_\alpha$, so it is compact by Tychonoff's theorem. Then each $E_A$ is a non-empty closed set and the class $(E_A:A\in\mathcal A)$ has the finite intersection property, so it has non-empty intersection. $\Box$

This theorem can be used to prove many nice results in infinite graph theory. For example:

Theorem (De Bruijn-Erdős): A graph $G$ is $k$-colourable if and only if every finite subgraph is $k$-colourable.

Proof: Let $X_v$ be the set $\{1,\dots,k\}$ (set of the $k$ colours) for each $v\in G$. Then, for any set $U\subset G$, a choice function for $(X_v:v\in U)$ is precisely a (not necessarily valid) colouring of the vertices in $U$ with $k$ colours. For each finite subgraph $A\subset G$, let $\phi_A$ be the given $k$-colouring of $A$. Then we have a colouring $\phi$ of $G$ satisfying the result of the above Theorem, which is easily shown to be a valid $k$-colouring; indeed, suppose instead that there are two vertices $u,v$ such that $\phi(u)=\phi(v)$. Then there exists some finite subgraph $B\supset\{u,v\}$ satisfying $\phi_B(u)=\phi(u)$ and $\phi_B(v)=\phi(v)$. So then $\phi_B(u)=\phi_B(v)$, contradicting $\phi_B$ being a valid $k$-colouring for $B$. $\Box$

We can also use the theorem to provide the following result.

Proposition: If every finite subgraph of a graph $G$ has a perfect matching then $G$ has a perfect matching.

  • $\begingroup$ Yes, you're right. I should probably delete this. $\endgroup$ – John Gowers Jul 17 '13 at 12:08
  • $\begingroup$ Hello, thank you for your answer. However, I don't understand why the theorems you presented are related to Tutte's theorem. Could you please explain? Thanks! $\endgroup$ – Tom Jul 27 '13 at 20:16

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.