Does a graph with seven vertices: one vertex of degree 1, one of degree 2, one of degree 3, … exist?

Question

Give an example of a simple and undirected graph for each one of the specified conditions, or reason why no such graph exists: A graph with seven vertices: one vertex of degree 1, one of degree 2, one of degree 3, two vertices of degree 4, one of degree 5, and one vertex of degree 6.

The sequence of the graph degree is : 1 + 2 + 3 + 4 + 4 + 5 + 6 = 25 degrees.

By using the Handshake theorem the total edges of the graph is : 25 / 2 = 12.5 which is an odd number - which means, the graph dosen't exist.

Correct or?

Answer 1

Your reasoning is correct. The handshake Lemma is a necessary condition for a graph to exist. It isn't sufficient though. Havel and Hakimi gave a characterization of degree sequences that are graphic, as did Erdos and Gallai.