Can there exist an uncountable planar graph?

Solution 1:

It depends on what you consider a plane drawing to be, but how about something like:

Put a vertex at $(0,0)$ and one at $(1,x)$ for every $x\in\mathbb R$, with a straight edge going between it and $(0,0)$.

Naively this seems to satisfy the requirements of a planar graph drawing: No point lies on two edges (except endpoints), no vertex lies on an edge it is not an endpoint of, every edge is represented by a continuous path between its endpoints.

On the other hand: A problem with this is that if we consider an abstract graph a topological space (with one point per vertex and a copy of the unit interval for each edge, stitched together in the obvious way), then the topology of the above drawing as a subspace of $\mathbb R^2$ is not the same as that of the graph.

Indeed if we define a "plane drawing" of a graph to be a subset of $\mathbb R^2$ which (with the subspace topology) is homeomorphic to the graph, then there can't be any uncountable planar graph, simply because there's no uncountable discrete subset of $\mathbb R^2$ that can be the image of the vertices.

On the other other hand: There are some topological subtleties hidden beneath "stitched together in the obvious way" here. Actually, as soon as there's a node with countable degree the most obvious way of stitching together (resulting in a quotient space) gives something that is not homeomorphic to a straightforward drawing of the graph -- such as a node at $(0,0)$ and one at $(1,n)$ for every $n\in\mathbb N$, with a straight edge to $(0,0)$. This can be fixed, though, by definig the stiching in a slightly more ad-hoc way which gives a different topology on the abstract graph.

Solution 2:

For another example, consider the graph with vertices $\{(0,x), (1,x) : x \in \mathbb{R} \setminus \mathbb{Q}\}$, and for each $x$ an edge between $(0,x)$ and $(1,x)$ represented by a horizontal line segment. In this case, for vertices $v,w$, there is an arc joining $v,w$ if and only if $v \sim w$.

You could make this connected by joining every vertex $(0,x)$ to $(-1,0)$ by a diagonal line segment.

As Henning says, as a subspace $A$ of $\mathbb{R}^2$ this is not homeomorphic to the graph $G$. However, there is a continuous injection $G \to A$.

For a more trivial example, consider the graph whose vertices are all the points $(x,y)$ where both $x,y$ are irrational, and with no edges. This has the same property.

Solution 3:

The following does not answer your question, but may be interesting.

Call a graph $G$ locally planar if every finite subgraph of $G$ is planar.

Let $F$ be an ordered field. The ordered pairs in $F\times F$ form a "plane." In this plane there is a natural definition of line segment.

Let $V$ be a collection of points of $F\times F$, and let $E$ be a collection of line segments joining some pairs of points of $V$ such that no two line segments in $E$ meet except possibly at endpoints. Then the pair $(V,E)$ defines a graph.

Let $G$ be a graph. Suppose that for the ordered field $F$, and some pair $(V,E)$ of the kind described above, the graph $G$ is isomorphic to the graph $(V,E)$. Then the graph $G$ will be called $F$-planar.

Then the following result holds. Let $\kappa$ be any infinite cardinal. Then there is an ordered field $F_{\kappa}$ such that any locally planar graph of cardinality $\kappa$ is $F_{\kappa}$-planar.

The proof is a straightforward Compactness argument. The field $F_{\kappa}$ can be taken to be an ultrapower of the reals.