В графе 24 ребра. Каждая вершина отнесена к 9 или степени 3, причем вершин степени 9, а сколько же, сколько вершин степени 3. Сколько вершин содержит граф?

Пусть x - количество вершин степени 9, и y - количество вершин степени 3. По условию x = y.

По лемме о рукопожатиях: 9x + 3y = 2 * 24 = 48.

Подставляя x = y: 9x + 3x = 48 => 12x = 48 => x = 4. Следовательно, y = 4. Общее количество вершин: x + y = 4 + 4 = 8.