Embedding of Tree

406 Views Asked by At

Q.

Proof for every Tree can be embedded into the plane.

Conditions.

We cannot use Euler Formula for Planar Graphs. We can use definition of tree, $V-E=1$, no-cycles, every edge is critical, there is a vertex of frequency at most one.

Attempt. We prove this by induction. True for $V$=1. Trivial. Consider true for $V<n$. Consider a tree $T$ with $n$ edges. Now, we know it has a vertex with at most one edge incident in it. Consider $T$\ $\{v,l\}$ the last vertex and edge. This can be embedded by inductive hypothesis. For the $v$ and $l$, that is left, it can be easily embedded.

The last part seems sloppy. I would appreciate other proofs or improvement on this proof.

2

There are 2 best solutions below

0
On BEST ANSWER

You may prefer to chose an embedding where all edges are mapped to straight line segments.

As you did, let $v$ be a vertex of degree $1$, let $w$ be its only neighbour. As you are not allowed to use very much, I assume you already know/can use that $v\ne w$ and removing vertex $v$ and edge $vw$ from $T$ does indeed produce a tree $T'$. By induction hypothesis, there is an embedding $f\colon T\to\mathbb R^2$ of $T'$ where all edges are mapped to straight line segments. Especially, the image of any edge $xy$ where $w\ne\{x,y\}$ is compact, hence has positive distance to $f(w)$. Since there are only finitely many such edges, for some $r>0$ the open ball $B_r(f(w))$ interscts only the finitely many straight line segments $f(wx)$ for edges incident with $w$. Select $f(v)$ in $B_r(f(w))\setminus\bigcup_{x\text{ neigbour of } w}f(wx)$ and map $vw$ to the straight line segment from $f(v)$ to $f(w)$.

1
On

You're right that there's something very subtle missing. Suppose we have a tree with uncountably many straight edges, from $(0,0)$ to every point on the circle $x^2+y^2=1$. Now you can't add another edge to $(0,0)$. However if your tree is finite your proof is fine.