# Proof for binary tree is a planar graph

Suppose G is a binary tree. Is G necessarily planar? Give a proof, or a counterexample.

My guess is that it is indeed planar but I am struggling to find a formal proof for this.

EDIT: Is there a proof that does not use Kuratowski's theorem? It was an exam question and we are not supposed to know that.

• Have you read about Kuratowski's theorem? – qaphla May 23 '14 at 23:50
• The only thing that comes to mind is Wagner's theorem, which works, but is serious overkill. This is a really intuitively obvious result, and it feels like there should be a simple, intuitive proof, but I don't know how to do it. – user2357112 supports Monica May 23 '14 at 23:50
• You can just give an explicit embedding of the graph into the plane. – Tunococ May 23 '14 at 23:51
• Oh, of course. Just assign coordinates to everything and verify there are no intersections. That was simple. – user2357112 supports Monica May 23 '14 at 23:52

We induct on the number of vertices of the tree, $G$, the case where $G$ has only one vertex being obvious. Every tree has a vertex with degree one, call it $v$ and call the vertex it is connected to $u$. Remove $v$ and by induction, $G - v$ can be drawn in the plane with no crossings. Now in a small enough neighborhood surrounding $u$ one will only find the edges that contain $u$ as an endpoint. In this neighborhood it is easy to put the edge $(u,v)$ in without creating any crossings.