На эти задачи не нужно писать программу, но придумать решение на бумаге. Напомним, что граф является простым, если в нем нет петель и кратных ребер. В этих задачах речь идет о простых неориентированных графах.

1. Сколько может иметь ребер граф на $$$n$$$ вершинах?
2. Докажите, что $$$m = \frac{1}{2} \sum deg_i$$$
3. Докажите, что в графе существуют, по крайней мере, $$$2$$$ вершины, степени которых равны.
4. Докажите, что в графе есть четное количество вершин, у которых степень нечетная.
5. Докажите, что если в графе степень каждой вершины не меньше $$$2$$$, то в графе есть цикл.
6. Работает ли это в обратную сторону? (Если в графе есть цикл, но степень каждой вершины не меньше $$$2$$$).
7. Докажите, что если в графе все вершины четные, то в графе нет мостов.
8. Дайте определение пути в графе между двумя вершинами.
9. Дайте определение циклу в графе между двумя вершинами.
10. Докажите, что если вам дан связный граф на $$$n$$$ вершинах и $$$n-1$$$ ребром, то в этом графе нет циклов.