Question

Let \(G\) be a countable graph, each finite subgraph of which is \(k\)-colourable. (i) Use König's lemma (Theorem 2.7) to prove that \(G\) is \(k\)-colourable. (ii) Deduce that every countable planar graph is 4-colourable.

Short answer

By constructing an infinite tree with each node representing a k-coloured finite subgraph of G and applying König's Lemma, it is concluded that the countable graph G is k-colourable. As every finite planar graph can be 4-coloured, then applying the above concept, every countable planar graph can also be 4-coloured.

Step-by-step solution

Proving G is \(k\)-colourable using König's Lemma

For proving \(G\) is \(k\)-colourable, consider constructing an infinite tree as follows: (a) Consider a root with label as an arbitrary chosen finite subgraph \(G_1\) of \(G\), and colour \(G_1\) with \(k\) colours; (b) The immediate successors of a node with label \(G_i\) represent all possible \(G_{i+1}\) obtained from \(G_i\) by adding one vertex more from \(G\). By the given condition that every finite subgraph of \(G\) can be k-coloured, possible \(k\)-colourings of these \(G_{i+1}\) are all the immediate successors from \(G_i\). By König's Lemma (which states that if every finite subtree of a finitely branching tree T has an infinite path, then T has an infinite path), there exists an infinite path in this tree, which specifies for each \(i\) an extension from a \(k\)-colouring of \(G_i\) to a \(k\)-colouring of \(G_{i+1}\). This path thereby gives a \(k\)-colouring of \(G\).

Proving every countable planar graph is 4-colourable

After proving \(G\) is \(k\)-colourable, let's now move towards proving every countable planar graph is 4-colourable. By 4-colour theorem, every finite planar graph can be coloured with no more than four colours. So for each finite subgraph of a countable planar graph, it can be 4-coloured. Applying the concept proved in Step 1 about \(G\) being \(k\)-colourable when each finite subgraph of it can be k-coloured, we can deduce that every countable planar graph can be colored with no more than four colours.

Key concepts

König's Lemma

König's Lemma is an important concept in graph theory and combinatorics. It essentially states that in any infinite, finitely branching tree, there exists an infinite path. Here's how it applies to graph colouring problems:
Imagine you have a tree where each node represents a possible colouring of a finite subgraph of a larger graph. For each node representing a colouring, its children represent possible extensions of this colouring to a slightly larger subgraph. König's Lemma guarantees that if all these finite subgraphs can be coloured, then there is a consistent way to extend these colourings to the entire graph, no matter how complex the graph becomes. This ensures that if every finite subgraph of our countable graph is k-colourable, we can find an infinite path that corresponds to a k-colouring of the entire graph.

• König's Lemma relies on the structure of trees and infinite paths.
• Useful for proving concepts about infinite graphs when their finite parts are manageable.
• Provides the backbone for showing that certain infinite graphs can be coloured.

This lemma is a foundational tool in helping us move from understanding finite graph properties to tackling infinite graphs.

4-Colour Theorem

The 4-colour theorem is a much-celebrated result in graph theory. It states that any planar graph can be coloured using no more than four colours such that no two adjacent vertices share the same colour. This theorem was proved using a combination of computer algorithms and human logic, marking an important milestone for computer-assisted proofs.
Overview of its implications:

• Essential for colouring maps with regions sharing a border.
• Ensures planarity constraints can be satisfied with minimal colours.
• Has practical applications in cartography and network design.

In the context of the provided exercise, after establishing that a countable graph can be k-coloured as per König's Lemma, the 4-colour theorem was applied specifically to planar graphs. By combining these concepts, every countable planar graph is shown to be 4-colourable. Essentially, this theorem simplifies the colouring challenge by assuring us that four colours are always enough, no matter how elaborate the plane graph.

Planar Graphs

Planar graphs are graphs that can be drawn on a plane without any of the edges crossing each other. They are significant in graph theory for their unique properties and constraints.
Some key points about planar graphs include:

• Can be visualized in 2D space without edge intersections, barring shared vertices.
• Obey Euler's formula: For any connected planar graph with vertices (V), edges (E), and faces (F), V - E + F = 2.
• Every finite subset of a planar graph can be coloured using the 4-colour theorem.

Planar graphs arise frequently in practical scenarios such as VLSI design, surrounding geography maps, and network layouts. In the given problem, understanding planar graphs is essential for linking the general idea of graph colourability (from infinite graphs using König's Lemma) to specific types (like planar graphs using the 4-colour theorem). Hence, understanding planar graphs helps ground abstract graph concepts into real-world applications.