0
$\begingroup$

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

$\endgroup$
1
  • 5
    $\begingroup$ The concept of "odd number" is somewhat useless when it comes to infinity :-) $\endgroup$ Commented Jul 16, 2013 at 22:18

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Yes, you're right. I should probably delete this. $\endgroup$ Commented Jul 17, 2013 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
    Commented Jul 27, 2013 at 20:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .