Question

Construct a simple graph of 12 vertices with two of them having degree 1,three having degree 3 and the remaining seven having degree 10

Answer 1

the complement graph, every vertex is adjacent to the vertices it was not adjacent to originally, so from the degree sequence of G12 we can obtain the degree sequence of H12. For example each of the 7 degree 10 vertices in G12 are adjacent to only one vertex in H12 (remember that their degree is at most 11, as they can't be adjacent to themselves).

So in H12 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 H12 is a tree. If we knew that H12 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 H12 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