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.

  • $\begingroup$ Have you read about Kuratowski's theorem? $\endgroup$ – qaphla May 23 '14 at 23:50
  • $\begingroup$ 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. $\endgroup$ – user2357112 supports Monica May 23 '14 at 23:50
  • 2
    $\begingroup$ You can just give an explicit embedding of the graph into the plane. $\endgroup$ – Tunococ May 23 '14 at 23:51
  • $\begingroup$ Oh, of course. Just assign coordinates to everything and verify there are no intersections. That was simple. $\endgroup$ – user2357112 supports Monica May 23 '14 at 23:52

Indeed it is true by Kuratowski's theorem or by the following argument which I will sketch below.

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.

| cite | improve this answer | |
  • 1
    $\begingroup$ Way more intuitive than using Kuratowski's theorem ! $\endgroup$ – Manuel Lafond May 24 '14 at 2:10

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.