Skip to main content

Section 7.1 Infinite Graphs

Previously we defined a graph as an ordered pair \(G = (V, E)\text{,}\) where \(V = \{v_1, v_2, ...\}\) is a set of vertices and \(E \subseteq \{\{a,b\} \st a, b \in V; a \ne b\}\) is a set of edges whose endpoints are vertices in \(V\text{.}\) So far all of the graphs we have considered had a finite set of vertices. There is however nothing in the definition of a graph that precludes the vertex set being infinite. In this section we will be considering such graphs. Specifically, we will be intersted in countably infinite vertex sets.

Definition 7.1.1.

Let \(G\) be a graph and \(k \ge 1\text{.}\) Then a \(k\)-coloring is a function \(c\) from \(V\) to \(\{1,2, ..., k\}\) where no two adjacent vertices are assigned the same color. A graph is \(k\)-colorable if it is possible to color the graph with \(k\) colors.

Suppose that every finite subgraph of \(G\) is colorable. Let \(G_i = (V_i, E_i)\) be a finite subgraph of \(G\text{.}\) Since \(G_i\) is a finite subgraph of \(G\) it is \(k\)-colorable. Let \(c_i\) be a \(k\)-coloring of \(G_i\text{.}\) We will use the \(c_i\) to create a \(k\)-coloring of \(G\text{.}\)

Let \(c(0)=x\) where \(x\) is the first color for which there are infinitly many \(i\) such that \(c_i(0)=x\text{.}\) Let \(c(n+1)=x\) where \(x\) is the first color for which there are infinitly many \(i\) such that for all \(j \lt n\) we have that \(c_j(y)=c(y)\) and \(c_i(x)=c(x)\text{.}\)

\(c\) is a \(k\)-coloring of \(G\text{.}\)

Now suppose that \(G\) is \(k\)-colorable. Then there exists a coloring, \(c\) which uses \(k\) colors. This same coloring can be applied to any subgraph of \(G\text{.}\)

Definition 7.1.3.

Let \(G=(A,B,E)\) be a bipartite graph. A function \(f:A\rightarrow B\) is an \(A\)-perfect matching for \(G\) if \(f\) is one-to-one and \(\forall a \in A\text{,}\) \(\{a,f(a)\}\in E\text{.}\) Given \(X\subseteq A\) and \(Y\subseteq B\text{,}\) we will sometimes call \(f:X\rightarrow Y\) a solution from \(X\) to \(Y\text{.}\)

\((\Rightarrow)\)

Suppose that for some finite \(X\subseteq A\text{,}\) \(|X|>|N_{G} (X)|\text{.}\)

Then there is no perfect matching for \(X\text{,}\) so there can be no \(A\)-perfect matching for \(G\text{.}\)

\((\Leftarrow)\)

Suppose that for all finite \(X\subseteq A\text{,}\) \(|X|\leq |N_{G} (X)|\text{.}\)

\(A\) is countable, so let \(A=\{a_{1} ,a_{2} ,...\}\text{.}\) Then given \(n\in \N\text{,}\) let \(A^{n} =\{ a_{1} ,a_{2} ,..., a_{n} \}\text{,}\) \(B^{n} =N_{G} (A^{n} )\text{,}\) \(E^{n} =E \cap \{ \{ a,b \} |a\in A^{n} ,b\in B^{n} \}\text{,}\) and \(G^{n} =(A^{n} ,B^{n} ,E^{n} )\text{.}\)

For \(n\in \N\text{,}\) \(G^{n}\) satisfies Hall's Theorem, so by the finite Hall's Theorem, there exists an \(A^{n}\)-perfect matching, say \(M^{n}\text{,}\) for \(G^{n}\text{.}\) We will build an \(A\)-perfect matching for \(G\) from the \(M^{n}\text{.}\)

Let \(M(a_{1} )\) be the first matching \((a_{1} ,b_{1} )\) such that for infinitely many \(s\text{,}\) \(M^{s} (a_{1} )=\{ (a_{1} ,b_{1} )\}\text{.}\) Then let \(M(a_{n+1} )\) be the first matching \((a_{n+1} ,b_{n+1} )\) such that for infinitely many \(s\text{,}\) \(M^{s} (a_{1} )=M(a_{1} ), M^{s} (a_{2} )=M(a_{2} ),...,M^{s} (a_{n} )=M(a_{n} )\text{,}\) and \(M^{s} (a_{n+1} )=\{ (a_{n+1} ,b_{n+1} )\}\text{.}\) Then \(M\) is an \(A\)-perfect matching for \(G\text{.}\)