Question

В графе из любой вершины выходит 5 или 7 ребер, причем есть как те, так и другие вершины. Всего ребер 25 Сколько вершин в графе?

Answer 1

Пусть в графе n вершин с 5-ю ребрами и m с 7-ю. Тогда удвоенное число ребер

$50 = 5m + 7n$

7n должно делиться на 5, поэтому единственный имеющий смысл вариант для n, это n=5

Значит 50 = 5m+35, откуда m = 3.

В графе 5+3=8 вершин.

Answer 2

Предположим, что в графе есть x вершин, из которых 5 ребер выходят из каждой вершины с 5 ребрами и 7 ребер выходят из каждой вершины с 7 ребрами.

Тогда общее количество ребер в графе можно выразить как:

5 * (количество вершин с 5 ребрами) + 7 * (количество вершин с 7 ребрами) = 25

Также из условия задачи известно, что есть как вершины с 5 ребрами, так и вершины с 7 ребрами. Поэтому:

количество вершин с 5 ребрами > 0 количество вершин с 7 ребрами > 0

Теперь решим систему уравнений:

5 * (количество вершин с 5 ребрами) + 7 * (количество вершин с 7 ребрами) = 25 количество вершин с 5 ребрами > 0 количество вершин с 7 ребрами > 0

Единственным целочисленным решением этой системы уравнений будет:

количество вершин с 5 ребрами = 2 количество вершин с 7 ребрами = 3

Таким образом, в графе имеется 2 + 3 = 5 вершин.