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.

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email