Planar Realization of a Graph in Three-Space We call a planar graph one that we can draw in two-space such that no two edges intersect. I was told that we're not so interested in drawing graphs in three-space, because it is "intuitively obvious" that we can just arrange the points and edges in a non-intersecting way because three-space gives us a great deal of room for arrangement.
While I agree that it seems intuitively true, I don't think it's necessarily true: it seems to me as if it might be possible to create a graph for which we cannot conceive a planar realization in three dimensions. If not, can we develop a formal proof that all graphs have a planar realization in three-space?
 A: First off, "planar realization in three-space" doesn't make much sense; the word "planar" means "in the plane", i.e., in two-space.
Yes, any (simple) graph can be realized in three-space, with the edges represented as nonintersecting straight line segments. You can do that by putting all the vertices on the twisted cubic curve $x=t,y=t^2,z=t^3$. Well, that works for any finite graph; for an infinite graph you need to assume that the vertex set has cardinality at most $2^{\aleph_0}$.
Proof. If there are two crossing edges with endpoints on that curve, then the endpoints are four coplanar points on the curve. Call the points $(t_i,t_i^2,t_i^3),\ i=1,2,3,4,$ where $t_1,t_2,t_3,t_4$ are distinct real numbers, and suppose they all lie on a plane $A+Bx+Cy+Dz=0$ where $A,B,C,D$ are not all zero. Then $A,B,C,D$ satisfy the equation
$$\left[\begin{matrix}1&t_1&t_1^2&t_1^3\\1&t_2&t_2^2&t_2^3\\1&t_3&t_3^2&t_3^3\\1&t_4&t_4^2&t_4^3\end{matrix}\right]\left[\begin{matrix}A\\B\\C\\D\end{matrix}\right]=\left[\begin{matrix}0\\0\\0\\0\end{matrix}\right].\tag1$$
However, since the coefficient matrix is a nonsingular Vandermonde matrix, the equation (1) has no nontrivial solution.
If you don't require a straight-line embedding, you can use the construction in the comment by alejopelaez, which also works for graphs with loops and multiple edges. Straight-line embeddings, of course, are only possible for simple graphs.
