122 На рисунке 13 (с. 80) изображён граф. Найдите степень вершины: a) A; б) Б. 123 На рисунках 19, а и 19, б (с. 81) изображены графы. Сколько у каждого из них вершин степени 0, степени 1 и степени 2? 124 Нарисуйте какой-либо граф, в котором 5 вершин со степенями 1, 2, 2, 3, 3. 125 Придумайте и нарисуйте два неодинаковых графа, в каждом из которых 6 вершин со степенями 1, 1, 2, 2, 3, 3. 126 Может ли количество вершин нечётной степени в каком-нибудь графе равняться: a) 0; б) 1; в) 2; г) 3; д) 4?

Задачи

122. (Требуется изображение графа на рисунке 13, которого нет в предоставленном изображении.)

123. (Требуется изображение графов на рисунках 19, а и 19, б, которых нет в предоставленном изображении.)

124. (Требуется нарисовать граф. Пример построения:

Вершины: A, B, C, D, E. Степени: deg(A)=1, deg(B)=2, deg(C)=2, deg(D)=3, deg(E)=3. Рёбра: AC, BD, CD, DE, BE.)

125. (Требуется нарисовать два неодинаковых графа. Пример:

Граф 1: Вершины: A, B, C, D, E, F. Степени: deg(A)=1, deg(B)=1, deg(C)=2, deg(D)=2, deg(E)=3, deg(F)=3. Рёбра: AC, BD, CE, DE, EF, CF.

Граф 2: Вершины: A, B, C, D, E, F. Степени: deg(A)=1, deg(B)=1, deg(C)=2, deg(D)=2, deg(E)=3, deg(F)=3. Рёбра: AF, BE, CD, CE, DE, EF.

126.

• a) 0: Может. Например, граф, состоящий только из вершин чётной степени (например, полный граф K_3 с вершинами степени 2).
• б) 1: Не может. Количество вершин нечётной степени всегда чётно.
• в) 2: Может. Например, граф, состоящий из двух вершин, соединённых одним ребром (две вершины степени 1).
• г) 3: Не может. Количество вершин нечётной степени всегда чётно.
• д) 4: Может. Например, граф, состоящий из четырёх вершин, каждая из которых имеет степень 3 (полный граф K_4).