Пусть в обоих графах вершины — A, B, C, D, E, F. Построим два графа с требуемыми степенями.

Граф 1: рёбра AB, AC, AD, BC, BE, DF. Степени вершин: A — 3, B — 3, C — 2, D — 2, E — 1, F — 1.

Граф 2: рёбра AB, AC, AD, BC, BF, DE. Степени вершин: A — 3, B — 3, C — 2, D — 2, E — 1, F — 1.

Эти графы получились одинаковыми с точностью до переименования вершин: во втором графе достаточно поменять местами названия E и F. Поэтому это не два неодинаковых графа. Для действительно неодинаковой пары можно взять первый граф и цикл из пяти вершин A–B–C–D–E–A с подвешенной к A вершиной F: у него степени будут 3, 2, 2, 2, 2, 1, то есть не требуемый набор.

Следовательно, приведённые рисунки не являются решением условия о двух неодинаковых графах: при заданном наборе степеней таких графов, отличающихся только структурой, нужно построить отдельно.

Поделись с друзьями