Show that every graph can be embedded in $\mathbb{R}^3$

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!

Solution 1:

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.

Solution 2:

Hint: To expand on the hint you were given. If you are able to show that you can put the vertices in such a way that no four of them are coplanar then you are done (Can you see why?).

Now, place the first three vertices, in light of my previous comment, where should you not place the fourth? and the fifth? etc.