[Math] Prove complement of this 12-vertex graph is a tree

Question

Let G₁₂ be a simple graph of 12 vertices, and H₁₂ its complement. It is known that G₁₂ has 7 vertices of degree 10, 2 vertices of degree 9, 1 vertex of degree 8 and 2 vertices of degree 7. Prove or disprove H₁₂ is a tree.

Answer 1

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).