Show that every graph can be embedded in $\mathbb{R}^3$ with all
edges straight.
(Hint: Embed the vertices inductively, where should you
not put the new vertex?)
I've also received a tip about using the curve ${(t, t^2 , t^3 : t \in \mathbb{R} )}$ but I'm not sure how to do that and how I should go about proving this rigorously but without using any pure topology.
Any hints or useful suggestions?
Thanks a lot!
Best Answer
Let $\vec{p} : \mathbb{R} \to \mathbb{R}^3$ be the function $\vec{p}(t) = (t, t^2, t^3)$ and $\mathscr{C}$ be the curve $\Big\{\;\vec{p}(t) : t \in \mathbb{R}\;\Big\}$.
For any four distinct $t_1, t_2, t_3, t_4$ in $\mathbb{R}$, the volume of the tetrahedron $\mathscr{T}$ formed by $\vec{p}(t_i) \in \mathscr{C}$ is proportional to a Vandermonde determinant:
$$\begin{align} 6 \text{Volume}(\mathscr{T}) & = \Big| (\vec{p}(t_2)-\vec{p}(t_1)) \cdot \left[ (\vec{p}(t_3) - \vec{p}(t_1)) \times (\vec{p}(t_4) - \vec{p}(t_1)) \right] \Big|\\ & = \det \begin{bmatrix} 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{bmatrix} \ne 0 \end{align}$$ The implies any four distinct points on $\mathscr{C}$ are not coplanar. As a result, the edges of the tetrahedron $\mathscr{T}$ intersect at and only at the appropriate vertices.
Now take arbitrary $n$ distinct points $\vec{p}_i$ from $\mathscr{C}$. Above argument shows that if we form a complete graph $K_n$ from them, the edges intersect at and only at appropriate vertices. This gives us an embedding of the complete graph $K_n$ into $\mathbb{R}^3$. Since every graph of $n$ vertices is a sub-graph of $K_n$, we are done.