13

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!

John Smith
  • 1,997
  • 1
    When you say embed you mean with no intersecting connections? What have you attempted? – Kevin Nov 28 '13 at 03:44
  • Do you mean finite graph? – Bruno Joyal Nov 28 '13 at 04:29
  • 1
    @BrunoJoyal He probably means finite graph, though cardinality at most $2^{\aleph_0}$ is all that's needed. – bof Nov 28 '13 at 04:34
  • 1
    This oddly titled question is not quite the same because the asker did not specify a straight-line embedding; however, one of the answers mentions the straight-line embedding. In fact, it merely gives the hint (which John Smith already has) to put the vertices on the twisted cubic curve $x=t,y=t^2,z=t^3$ without giving further details; but showing that no four points on that curve are coplanar should be an easy enough exercise. – bof Nov 28 '13 at 04:38

3 Answers3

16

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.

achille hui
  • 122,701
  • 1
    And of course the same goes for an infinite graph, unless the number of vertices exceeds the continuum. – bof Nov 28 '13 at 04:44
  • 1
    Worth noting that this is known as a Moment Curve (https://en.wikipedia.org/wiki/Moment_curve) and has a lot of applications because of the lack of coplanarity. – Steven Stadnicki Jan 15 '20 at 23:50
  • Two remarks: 1) You don't need to get fancy with Vandermonde determinant. If four points of twisted cubic are on the plane ax+by+cz=d then at+bt^2+ct^3=d has 4 solutions. 2) For infinite graphs you get an injection, but it's unclear whether you get an embedding (I think you do if the graph is locally finite and you choose your points to go off to infinity, and you don't for the CW topology otherwise; it's not clear to me what the answer is for other topologies on the graph). – Max May 31 '21 at 17:19
5

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.

alejopelaez
  • 2,707
-2

A graph can be seen as a manifold; there is a result that the graph of a smooth function is a manifold; in this case, it is a 1-manifold. Then use Whitney's theorem that guarantees that a smooth m-manifold can be smoothly-embedded in $\mathbb R^{2m}$.

user99680
  • 6,708
  • I suspect that the OP is using "graph" in a different context, here, but we'll have to see. – Cameron Buie Nov 28 '13 at 03:48
  • @CameronBuie It's quite obvious that the graphs in question are not manifolds, they are $1$-complexes. The Menger-Nöbeling theorem guarantees that any $n$-dimensional separable metric space embeds topologically in $\mathbb R^{2n+1}$, so any graph is topologically embeddable in $\mathbb R^3$, but that doesn't take care of the straight line requirement. – bof Nov 28 '13 at 04:29
  • I think a very small homotopy would turn a graph into a manifold, to complete an embedding. – user99680 Nov 28 '13 at 04:32