# Prove complement of this 12-vertex graph is a tree

Let G12 be a simple graph of 12 vertices, and H12 its complement. It is known that G12 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 H12 is a tree.

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

This is a matter of whether you can create a complement graph that is disconnected or not: when the number of edges is 1 less than the number of nodes as in your $Q$, the complement graph is a tree iff it is connected.

Whenever you can come up with a complement graph that is a tree with these numbers, you can modify it to be a disconnected graph with the same number of nodes and edge distribution among nodes: take two leaves in the tree where they have different parents. remove these leaves and connect them with an edge so that the two are connected with one another and disconnected from the rest. Put an edge connecting the parents of these two leaves. The disturbed nodes preserve their degree in the resulting graph and the resulting graph is disconnected with the same number of edges. A disconnected graph with 11 edges can be turned into a tree in a similar way.

Your $Q$ has no solution for disproving or proving it on one side. the resulting graph can be either.

• @martini which part of my answer have you edited ? i don't see any changes if you haven't worked on a puctuation mark somewhere – ashley Nov 21 '12 at 17:46
• I added LaTeX-\$for your$Q$s. – martini Nov 21 '12 at 20:18 We can exhaustively enumerate (up to isomorphism) the trees on$12$vertices and vertex degrees between$1$and$4$using geng which comes with nauty. geng 12 11:11 -c -d1 -D4  Trees on$12$vertices have$11$edges (hence 11:11 above); the -c implies we count only connected graphs. This generates 355 trees, and using a script we can exclude the ones that don't have the degree sequence$(1,1,1,1,1,1,1,2,2,3,4,4)$. This results in the following$28$graphs: Using a similar process, we can find there are$106$graphs (up to isomorphism) that satisfy the constraints on$H_{12}\$. The disconnected ones are: