combinatoricsdiscrete mathematicsgraph theory
I managed to prove the second part – that a tree that is one vertex with n-1 degree and all the rest are connected to it – the complement graph of such tree is an isolated vertex and the rest of the vertices form a full graph.
Now, I cant get to prove it for the other option – i.e if every vertex in the tree is of degree $1\leq d(v) < n-2$ than the complement graph is connected.
In the complement graph, every vertex is adjacent to the vertices it was not adjacent to originally, so from the degree sequence of $G_{12}$ we can obtain the degree sequence of $H_{12}$. For example each of the 7 degree 10 vertices in $G_{12}$ are adjacent to only one vertex in $H_{12}$ (remember that their degree is at most 11, as they can't be adjacent to themselves).
So in $H_{12}$ we have seven vertices of degree 1, two vertices of degree 2, one vertex of degree 3 and two vertices of degree 4.
Given this sequence we now want to know if $H_{12}$ is a tree. If we knew that $H_{12}$ was connected, we could just count the number of edges (a connected graph on $n$ vertices with exactly $n-1$ edges is a tree - not a bad exercise in itself), so if we assume $H_{12}$ is connected, we can count the edges (half the sum of the degrees) and see that it is a tree. We can go a little further by actually drawing the graph, which we can do by (going back small step) asking whether the degree sequence is graphic. In this case we have the sequence $\{4,4,3,2,2,1,1,1,1,1,1,1\}$. This sequence is graphic if and only if the sequence $\{3,2,1,1,1,1,1,1,1,1,1\}$ is graphic - what this implies is that we can construct the graph by taking the vertex of largest degree $d$ and assuming it is adjacent the next $d$ vertices of largest degree. Then one vertex is taken care of, and $d$ of the remaining vertices have one of their edges taken care of. Applying this to our sequence we get:
However this is not the only graph with this degree sequence, there are other possibilities, at least one of which (I checked) has a cycle. So really what we have is that there is at least one possible graph fitting the description of $G_{12}$ that has a complement graph $H_{12}$ that is a tree.
If you want a more arcane test, you can construct a multinomial with the degree sequence that has integer solutions if and only if the sequence can be realized as a tree (Gupta, Joshi & Tripathi, 2007).
Since $G$ is connected, it has a spanning tree. You can delete any leaf $v$ from the spanning tree and the graph still has a spanning tree, so is still connected.
Best Answer
Assume that the graph is not connected. Then, separate the graph into 2 separate graphs. Now, all the missing edges between the 2 components must have belonged to the tree. Suppose the size of the 2 components is a and b. (size of a component refers to the number of vertices in it).
Then, we have : $$ a + b = n $$ and $$ a*b \le (n-1) $$ (because the number of edges in a tree can't be more than that).
The only way this can happen is when a=n-1 and b=1 , which is the second part of your question.