# Math Help - 8,7,7,7,7,3,3,3,3,2 a Possible Graph?

1. ## 8,7,7,7,7,3,3,3,3,2 a Possible Graph?

Q: Can a graph of order 10 have one vertex of degree 8, four vertices of degree 7, four of degree 3, and one of degree 2?

That is, can the graph 8,7,7,7,7,3,3,3,3,2 exist?

I am told the answer is no. However, for multigraphs yes this is possible. I don't know why. I have tried using the Handshake Theorem, but that doesn't tell me much.

Does anybody know which theorem proves that the graph above cannot exist unless it is a multigraph? What is the reason why it cannot exist?

2. No, it's not a possible graph. We can prove this fact by using the following theorem:

Theorem: If the sequence r,s_1,s_2,...,s_r,t_1,t_2,...,t_k is a degree sequence of graph with r+k+1 vertices, then the sequence s_1 - 1,s_2 - 1,...,s_r -1,t_1,t_2,...,t_k (rearranged in a decreasing way) is a degree sequence of a graph with r+k vertices.

Step 1.a: 8|7,7,7,7,3,3,3,3|2
Step 1.b: 6,6,6,6,2,2,2,2,2
Step 1.c: 6,6,6,6,2,2,2,2,2(rearranged but remained same)

Step 2.a: 6|6,6,6,2,2,2|2,2
Step 2.b: 5,5,5,1,1,1,2,2
Step 2.c: 5,5,5,2,2,1,1

Step 3.a: 5|5,5,2,2,1|1
Step 3.b: 4,4,1,1,1,1
Step 3.c: 4,4,1,1,1,1

Now without going any further, one can show that this cannot be a degree sequence of a simple graph.

3. Not sure if this is correct but nothing sticks out to me:

The complete graph $K_{n}$ has at most $\frac {1}{2}n(n+1)$ edges. For n = 10, this gives 55.

Your graph has 50 edges and 10 vertices, so you need to remove 5 edges from $K_{10}$. Note that $K_{10}$ has all vertices with degree 9, so removing 5 can never leave one vertex with a degree of 2. Therefore the stated graph cannot exist.

4. For this question, your method is definitely much more efficient than the algorithm i gave. But in general, we encounter with more complicated situations and it's better to use the degree-sequence algorithm.

5. Originally Posted by Thomas154321
Not sure if this is correct Your graph has 50 edges and 10 vertices
There is a problem with that solution.
The degree sum is twice the number of edges.
Therefore, the number of edges is 25 not 50.