A space-filling complete graph.
A straight-line embedding of a graph \(G\) into \(\mathbb R^3\) is an injective mapping \(f\: V(G)\rightarrow \mathbb R^3\) such that the open segments \((f(u),f(v))\), \(\{u,v\} \in E(G)\), are pairwise disjoint and also disjoint from the images of all vertices. It is shown that any graph \(G\) with \(| V(G)| = \mathfrak c\) (continuum) and containing a matching of cardinality \(\mathfrak c\) has a space-filling straight-line embedding, i.e.\ one with \((\bigcup _{v\in V(G)} f(v))\cup (\bigcup _{\{u,v\}\in E(G)} (f(u),f(v))) = \mathbb R^3\). The proof proceeds by transfinite induction and uses the axiom of choice. It is also shown that a graph whose edges can be covered by finitely many vertices does not have a space-filling straight-line embedding into the plane. The analogous question for \(\mathbb R^3\) remains open.
scientific article; zbMATH DE number 1600971