I am currently reading Trudeau's introductory book on Graph Theory and have just come across the concept of planar and non-planar graphs. The definition reads: 'A graph is planar if it is isomorphic to a graph that has been drawn in a plane without edge-crossings'. My question is, if the definition is changed slightly, and we replace 'plane' with '3D space', does this lead to all possible finite graphs being planar? Or to put it more simply (I think), is there a graph which cannot be drawn without edge crossings in 3D space? And if not how can one prove that such a graph would not exist?
I apologize if this question is trivial; I thought of graphs only as representations of functions until yesterday.
Best Answer
A finite graph has a finite vertex set $V=\{v_1,v_2,\ldots, v_n\}$. Arrange these vertices as points $v_k=(k,0,0)$ $(1\leq k\leq n)$ on the $x$-axis of ${\mathbb R}^3$. Some pairs $v_i$, $v_j$ $(i\ne j)$ are joined by an edge. Assume there are $N\leq{n\choose2}$ edges. Choose $N$ different planes containing the $x$-axis, and draw each occurring edge $\{v_i,v_j\}$ as a half circle connecting $v_i$ with $v_j$ in one of these planes. The $N$ edges will then not intersect.
By the way: Graphs of functions and graphs studied here have nothing in common. It's a semantic accident that the two completely different things have obtained the same name.