Suppose a tree graph T with $n\ge 4$ ,and 3 edges $e_1,e_2,e_3$ from its complement tree graph T-.Show that $G = T + e_1 + e_2 +e_3$ is a planar graph

Question

can't seem to find the proof for this problem. I know that a Tree graph has the property: $n = m - 1$ where $n$ is the number vertices and $m$ is the number of edges. Also not sure if the restriction for planar graphs $m \le 3n - 6$ is sufficient to prove that a graph will be planar, as there are graphs that are not planar that satisfy the requirement $m \le 3n - 6$. I believe graph $G$ will basically be graph $T$ with all its vertices connected but I can't see how that helps me prove it's a planar graph. Thanks in advance!

Answer 1

A tree with $n$ vertices has $n-1$ edges; when we add three more, we get $n+2$. You should begin by proving the following stronger claim: in any $k$-vertex subgraph of $T + e_1 + e_2 + e_3$, there are at most $k+2$ edges.

(Hint: what is the maximum number of edges in a $k$-vertex subgraph of $T$?)

Meanwhile, a graph is planar unless it contains a subdivision of either $K_{3,3}$ or $K_5$. You can show that:

• A $k$-vertex graph which is a subdivision of $K_{3,3}$ contains $k+3$ edges.
• A $k$-vertex graph which is a subdivision of $K_5$ contains $k+5$ edges.

(Hint: what happens to the vertex and edge count when we subdivide an edge?)

Putting these facts together, we conclude that $T + e_1 + e_2 + e_3$ cannot contain a subdivision of $K_{3,3}$ or $K_5$, so it must be planar.