I am trying to show that the graph complement of a tree graph $G$ is connected or has a unique isolated vertex and and the remaining nodes with its respective edges form a complete subgraph of $G$.
In order to prove this property I divided the problem in two cases:
Suppose $n$ is the number of nodes in $G$
1) There exists $v$ such that $deg_{G}(v) = n-1$ and for all $w \in G \setminus \{v\}$, $deg_{G}(w) = 1$ (the number of leaves is at least $n-1$).
2) The number of leaves is less than $n-1$.
Now let $\overline{G}$ be the complement graph of $G$. If we are in case 1), by definition of complement graph, we have then $deg_{\overline{G}}(v) = n-1 – (n-1) = 0$ and $deg_{\overline{G}}(
w) = n-1 – 1 = n-2$ for any $w \neq v$. So if $K_{n-1}$ is the complete graph of $n-1$ nodes, then we have that $\overline{G} = K_{n-1} \cup \{v\}$.
I don't know what to do in case 2) to show that $\overline{G}$ is connected, any ideas would be greatly appreciated. Thanks in advance.
Best Answer
I won't finish your proof, but I'll give you some notes and hints.
First, whenever you break into cases, make it clear that the cases are exhaustive. Here your cases might be labeled as "the number of leaves is $n-1$" and "the number of leaves is not $n-1$". In the latter cases, you can deduce the information that you have started off case 1 with. (This is more of a note about logical/structured writing; your math is sound here.)
Second, we can try to borrow ideas from classic problems to solve other problems. This problem in particular reminded me of the remark of Erdős: "a graph or its complement is connected." If you aren't familiar with the proof of this fact, it goes something like this: suppose $G$ is not connected. Then $G$ must have two connected components $A$ and $B$. We can now show that every vertex of $A$ is connected to every vertex of $B$ in $\overline{G}$. However, we are not done yet; we can also show that every vertex of $A$ is connected to every other vertex of $A$ through a vertex of $B$ (and same for $B$).
Now that you know this proof, think about how that idea may be applied in your case 2.