Диаграмма неориентированного графа состоит из сторон правильного шестиугольника ABCDEF и трех его диагоналей AD, BE, FC. Сколько вершин степени два имеет подграф, полученный в результате объединения подграфа, порожденного вершинами A,B,C,F, и подграфа, порожденного вершинами A,B,C,E?
Рассмотрим по шагам задание.
Исходный граф построен на правильном шестиугольнике с вершинами A, B, C, D, E, F. В нём есть стороны шестиугольника (AB, BC, CD, DE, EF, FA) и три диагонали (AD, BE, FC).
Определим два подграфа: • Подграф 1 порожден вершинами {A, B, C, F}. • Подграф 2 порожден вершинами {A, B, C, E}.
В подграфе 1 (вершины A, B, C, F) в исходном графе присутствуют следующие ребра: – AB (сторона шести...