Infinite planar graph

694 Views Asked by At

Let $G$ be a simple undirected graph such that $G=\underset{i\in I}{\cup}G_i$, $G_i=K_j, j=1,2,3,4$ ($K_j$ denotes the complete graph) and $|I| \leq c$, where $c$ is the cardinality of the real number. Is the graph $G$ planar? If so, is it necessary that $|I|\leq c$?

1

There are 1 best solutions below

2
On BEST ANSWER

Since a planar embedding is especially an injective map $V\to\mathbb R^2$, the condition $|I|\le c$ is clearly necessary.

The remaining arguments may depend on how planar embedding is defined exactly in the presence of infinite graphs. If it is only (i.e. without any "separatio" assumptions) an injective map $f\colon V\to \mathbb R$ together with continuous maps $f_{ab}\colon[0,1]\to \mathbb R^2$ for all edges $ab$ with $f_{ab}(0)=a$, $f_{ab}(1)=b$ and $f_{ab}(x)=f_{cd}(y)$ only if $x,y\in\{0,1\}$ or $ab=cd$ and $x=y$, then there is no need to keep distinct vertices or edges apart from each other: There is no problem in placing $c$ many copies of $K_1$ on a line segment, or $c$ many copies of $K_2$ on a square (in form of vertical lines, say). Also, $c$ many copies of $K_3$ can be realized as nested triangles.

But with more than countably many copies of $K_4$ we get into trouble: Each embedding of a $K_4$ contains at leat one rational point in the interior of each of its three bounded faces. Since there are only countably many triples of rational points, there must be two distinct embeddings of $K_4$ for which we picked the same triple. This is not possible (why?)