Let $T$ be a tree of order $n$.Show that $T$ is isomorphic to a subgraph of $\overline{C}_{n+2}$

Question

Let $T$ be a tree of order $n$.Show that $T$ is isomorphic to a subgraph of $\overline{C}_{n+2}$

I'm allowed to use this theorem: for every tree $T$ of order $k$. If $G$ is a graph such that $\delta(G) \geq k-1$ then $G$ contain a subgraph isomorphic to $T$.

Since the smallest cycle has $3$ vertices so I let $n \geq 1$. I tried to prove this by induction

Base : $n=1$. In this case we have $T$ is just a point, which isomorphic to a subgraph of $\overline{C}_3$. So the base case is good.

Suppose the statment is true for $n=k>1$. Meaning $T$ is isomorphic to a subgraph of $\overline{C}_{k+2}$ and $\delta(\overline{C}_{k+2})\geq k-1$ . Now if I added one vertex into $T$ I'm not sure how to show $\delta(\overline {C}_{k+3})\geq k$

Answer 1

Induction makes this more complicated than necessary. The result follows almost immediately from the theorem.

Let $T$ be a tree of order $n$ and consider $G=\overline{C}_{n+2}$. Every vertex in $G$ is adjacent to all but two of the other vertices, so $\delta(G)=n-1$ and hence $G$ contains a subgraph isomorphic to $T$.