99. Постройте два неизоморфных остовных дерева графа, изображённого на рисунке 55.

Обозначим вершины графа по уровням слева направо: верхний уровень — \(A,B,C\), затем \(D,E\), затем \(F,G\), нижний уровень — \(H,I\).

Два неизоморфных остовных дерева можно задать следующими наборами рёбер:

1. \(AB, AC, BD, DE, DF, EG, FH, GI\). Это дерево имеет вершину степени 3.
2. \(AB, BC, BD, CE, DF, EG, FH, GI\). Это дерево имеет другой набор степеней вершин, поэтому оно неизоморфно первому.

В каждом наборе 8 вершин и 7 рёбер, а циклов нет, следовательно, оба графа являются остовными деревьями.

Ответ: приведены два неизоморфных остовных дерева.