Graph score
Task number: 3843
The sequence \((1{,}1,2{,}2,2{,}4)\)
- is not a graph score;
- is a graph score, but the graph may not be connected;
- is a graph score and the graph must be connected.
Solution
If we add two leaves to a four-cycle, we get one of the possible graphs with the given score.
Alternatively, you can verify that it is a graph score by using the score theorem: \( (1{,}1,2{,}2,2{,}4) \to (1{,}0,1{,}1,1) \to (0{,}1,1{,}1,1) \to (0{,}1,1{,}0) \to (0{,}0,1{,}1) \to (0{,}0,0) \)
If the graph would be disconnected, then the component that contains a degree 4 vertex must have at least 5 vertices. The graph does not have isolated vertices, so each component has at least two vertices. Together we have 6 vertices, on which components of the stated sizes: at least 5 and at least 2, cannot be built.
Answer
The correct answer is c.
