Collection of Maths Problems

Graph by score

Task number: 4170

• Variant

  \((1{,}1,1{,}2,2{,}3,4{,}4,5{,}5)\)

• Solution

  According to the theorem about score:

  \( (1{,}1,1{,}2,2{,}3,4{,}4,5{,}5)\to (1{,}1,1{,}1,2{,}2,3{,}3,4)\to (1{,}1,1{,}1,1{,}1,2{,}2)\to (0{,}1,1{,}1,1{,}1,1)\to (0{,}0,1{,}1,1{,}1)\to \)

  \(\to (0{,}0,0{,}1,1)\to (0{,}0,0{,}0) \)

  The resulting sequence is the score of the graph without edges on the four vertices, so the original sequence is the score of a graph.

  We create a graph by gradually adding vertices so that the created graphs have the sequence of the sequences we found during the reduction:

  

• Answer

  The given sequence is the score of a graph.

• Variant

  \((1{,}2,3{,}4,5{,}5,6)\)

• Solution

  According to the theorem about score:

  \( (1{,}2,3{,}4,5{,}5,6)\to (0{,}1,2{,}3,4{,}4)\to (0{,}0,1{,}2,3)\to (-1{,}0,0{,}1) \)

  The resulting sequence is not the score of any graph, so the original sequence is not the score of any graph.

• Answer

  The given sequence is not the score of a graph.

• Variant

  \((3{,}3,3{,}4,5{,}5,5{,}6)\)

• Answer

  The given sequence is the score of a graph.

• Variant

  \((1{,}2,2{,}3,3{,}4,6{,}7)\)

• Answer

  The given sequence is the score of a graph.

• Variant

  \((1{,}1,4{,}5,5{,}6,6{,}6)\)

• Answer

  The given sequence is not the score of a graph.

• Variant

  \((1{,}3,3{,}4,5{,}5,6{,}7)\)

• Answer

  The given sequence is the score of a graph.