№6. На карте показаны 6 городов, между которыми проложены дороги (рёбра). Города обозначены буквами: A, B, C, D, E, F. Ниже представлено описание дорог: A соединён с B, C и D; B соединён с A, D и E; C соединён с A и D; D соединён с A, B, C и F; E соединён только с B; F соединён только с D. 1) Постройте данный граф. 2) Определите степень (валентность) каждой вершины. 3) Сколько всего рёбер в графе? 4) Найдите сумму степеней всех вершин. Совпадает ли она с удвоенным числом рёбер? 5) Существует ли цепь из A в F, не повторяя рёбер? 6) Существует ли цикл, проходящий через вершины A → C → D → A?

Учитываем каждую дорогу только один раз. Рёбра графа: AB, AC, AD, BD, BE, CD, DF.

1. Степени вершин: \(d(A)=3\), \(d(B)=3\), \(d(C)=2\), \(d(D)=4\), \(d(E)=1\), \(d(F)=1\).
2. Число рёбер: \(|E|=7\).
3. Сумма степеней: \(3+3+2+4+1+1=14\).
4. Удвоенное число рёбер: \(2\cdot7=14\). Сумма степеней совпадает с удвоенным числом рёбер, что подтверждает теорему о рукопожатиях.
5. Цепь из A в F существует: A–D–F. Рёбра не повторяются.
6. Цикл A → C → D → A существует, так как присутствуют рёбра AC, CD и DA.

Ответ: 7 рёбер; степени вершин — 3, 3, 2, 4, 1, 1; сумма степеней 14=2·7; цепь A–D–F и цикл A–C–D–A существуют.