10
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ When you say embed you mean with no intersecting connections? What have you attempted? $\endgroup$ – Kevin Nov 28 '13 at 3:44
  • $\begingroup$ Do you mean finite graph? $\endgroup$ – Bruno Joyal Nov 28 '13 at 4:29
  • 1
    $\begingroup$ @BrunoJoyal He probably means finite graph, though cardinality at most $2^{\aleph_0}$ is all that's needed. $\endgroup$ – bof Nov 28 '13 at 4:34
  • 1
    $\begingroup$ 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. $\endgroup$ – bof Nov 28 '13 at 4:38
11
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ And of course the same goes for an infinite graph, unless the number of vertices exceeds the continuum. $\endgroup$ – bof Nov 28 '13 at 4:44
  • $\begingroup$ Worth noting that this is known as a Moment Curve (en.wikipedia.org/wiki/Moment_curve) and has a lot of applications because of the lack of coplanarity. $\endgroup$ – Steven Stadnicki Jan 15 at 23:50
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
-2
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I suspect that the OP is using "graph" in a different context, here, but we'll have to see. $\endgroup$ – Cameron Buie Nov 28 '13 at 3:48
  • $\begingroup$ @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. $\endgroup$ – bof Nov 28 '13 at 4:29
  • $\begingroup$ I think a very small homotopy would turn a graph into a manifold, to complete an embedding. $\endgroup$ – user99680 Nov 28 '13 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.