V
V
Viva88882021-09-29 23:01:28
Mathematics
Viva8888, 2021-09-29 23:01:28

Does there exist a graph on 9 vertices whose degrees are 1, 1, 1, 1, 1, 2, 4, 5, 6?

Is my proof correct? What to do for large sequences? What is the algorithm for doc-va such tasks?
I prove it as follows.
Let's say that all vertices have degree 0
0 0 0 0 0 0 0 0 0
Then to get a vertex with degree 6 we need to add edges
0 0 1 1 1 1 1 1 6
Here I connected the last vertex with 3,4,5, 6,7,8 vertices, and their degree has increased by 1
Now we need to get a vertex with degree 5
1 1 1 1 1 2 2 5 6
Next we need to get a vertex with degree 4
1 1 1 1 2 3 4 5 6
Contradiction

Answer the question

In order to leave comments, you need to log in

2 answer(s)
R
Rsa97, 2021-09-29
@Rsa97

Erdős-Gallay theorem
1. 8 ≥ 6 ≥ 5 ≥ 4 ≥ 2 ≥ 1 ≥ 1 ≥ 1 ≥ 1 ≥ 1
2. 6 + 5 + 4 + 2 + 1 + 1 + 1 + 1 + 1 = 22
This sequence is correct .
k = 1, 6 ≤ (0 + 8), satisfied,
k = 2, 11 ≤ (2 + 9), satisfied,
k = 3, 15 ≤ (6 + 7), not satisfied.
This means that this sequence is not graphic, and it is impossible to construct a simple graph from it.

A
Alexandroppolus, 2021-09-29
@Alexandroppolus

Specifically, here you can think of it like this:
vertices 4, 5, 6, even if they are connected to each other in pairs (which will take 6 degrees), they still have 9 free degrees that are not covered by the rest of the vertices.
but this is provided that there are no multiple edges (when edges A and B are connected by more than one vertex), and loops (edges A-A). Do you have the exact same case?

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question