Какие задачи в теории графов связаны с количеством ребер и вершин?

Некоторые задачи в теории графов, связанные с количеством рёбер и вершин:

• Задача о рукопожатиях. 3 Если собралось N человек (вершин) и каждый с каждым обменялся рукопожатием (ребро), сколько всего было рукопожатий? 3
• Задача о Кенигсбергских мостах. 14 Нужно выбрать такой маршрут, чтобы пройти один и только один раз по каждому мосту и затем вернуться в начальную точку пути. 4
• Задача о диагоналях в 17-угольнике. 4 Вершины 17-угольника — вершины графа, диагонали и стороны — рёбра графа. 4 Нужно определить, сколько диагоналей в таком графе. 4
• Задача о тропинках между домами. 4 Пусть дома — вершины графа, тропинки — рёбра. 4 Нужно определить, сколько всего тропинок проходит между домами. 4

Также к задачам, связанным с количеством рёбер и вершин, относится определение степени вершины — количества рёбер, которые выходят из неё. 23