Extending Kuratowski's planarity theorem on finite graphs to countable infinite graphs.

584 Views Asked by At

As the title suggests. Kuratowski's theorem states that a graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_3,_3$

I want to extend this result to "A infinite graph G with a countable number of vertices is planar if and only if any finite subgraph of G does not contain a subdivision of $K_5$ or $K_3,_3$.

2

There are 2 best solutions below

0
On BEST ANSWER

The proof boils down to: Suppose $G$ is countable and every finite subgraph of $G$ is planar. Then $G$ is planar. Here are some ideas. We can assume that $G$ is countably infinite. Let $\{x_k : k \geq 1\}$ list the vertices of $G$. Let $G_k$ be the induced subgraph of $G$ on $\{x_i : i \leq k\}$. Then each $G_k$ is planar. We would like to combine plane drawings of $G_k$'s to get a plane drawing of $G$. Construct a graph $P$ whose vertices are plane drawings of $G_k$'s and there is an edge between two vertices $p_1, p_2$ iff for some $k$, $p_1$ is a plane drawing of $G_k$, $p_2$ is a plane drawing of $G_{k+1}$ and $p_2$ restricted to $G_k$ is topologically equivalent to $p_1$. Note that $P$ is an infinite tree in which each vertex has finite degree. By Konig's lemma, $T$ has an infinite path which can be taken to be $p_1, p_2. p_3, \dots$ where each $p_k$ is a plane drawing of $G_k$. Now it is straightforward to construct a plane drawing of $G$ as follows. Suppose we have already constructed a plane drawing $q_k$ of $G_k$ which is topologically equivalent to $p_k$. Extend $q_k$ to a plane drawing of $G_{k+1}$ topologically equivalent to $p_{k+1}$. Then the union of $q_k$'s is the required drawing of $G$.

3
On

It's been done. The countable version was done by Erdös (who else?) and the uncountable version by Wagner. Wagner proved that a graph is planar iff it has at most continuumly many $=|\mathbb{R}|$ vertices, no $K_5$ or $K_{3,3}$ subdivision, and at most countably many vertices of degree $\ge 3$.

The source for the Wagner paper is

K. WAGNER, "Fästplattbare Graphen", J. Combinatorial Theory 3 (1967), 326-365.

I don't have a reference for the Erdös paper.