Question

Вершины дерева покрашены в красный и синий цвета так, что смежные вершины имеют разные цвета, и красных вершин не меньше, чем синих. Докажите, что хотя бы одна из висячих вершин покрашена в красный цвет. Требуется полное доказательство задачи. Решить до 3 февраля.

Answer 1

Случай с двумя вершинами очевиден. Далее рассматриваем случаи с большим числом вершин.

Пойдем от противного: пусть не так, и все висячие вершины покрашены в синий цвет.

Подвесим дерево за какую-нибудь красную вершину (такая обязательно существует, т.к. красных вершин не меньше, чем синих).

Получим, что цвет всех вершин уровня 0 красный. Но тогда, в силу того, что смежные вершины имеют разные цвета, цвет уровня 1 синий. Аналогично, цвет уровня 2 красный и т.д.

То есть цвета вершин на каждом из уровней одинаковы, и при этом на четных уровнях цвет вершин красный, а на нечетных - синий.

Степень красной вершины уровня 0 не может быть равна единице, т.к. все висячие вершины по предположению синие. Значит, ее степень не меньше двух, откуда число вершин уровня 1 не меньше двух - т.е. больше числа вершин уровня 0.

Рассмотрим пару из красного уровня 2k и синего уровня 2k+1, k∈N. Рассмотрим вершину красного уровня. Ее степень не меньше единицы (благодаря родительской вершине уровня 2k-1). Но при этом, т.к. все висячие вершины по предположению синие, ее степень должна быть не меньше двух - т.е. из нее выходит не менее одной дочерней синей вершины. Повторяя эти рассуждения для каждой из вершин уровня 2k, получим, что число вершин синего уровня не меньше числа вершин красного уровня.

Повторяя эти рассуждения для оставшихся уровней и учитывая, что число вершин уровня 1 больше числа вершин уровня 0, получим, что число синих вершин больше числа красных вершин - противоречие.

Значит, предположение неверно, и хотя бы одна из висячих вершин покрашена в красный цвет.

Ч.т.д.

Answer 2

Problem Statement

The problem states that the vertices of a tree are colored in red and blue such that adjacent vertices have different colors, and there are at least as many red vertices as blue vertices. The task is to prove that at least one of the leaf vertices (also known as hanging vertices) is colored red.

Proof

To prove this, let's consider a tree with n vertices, where n > 2. We will use a proof by contradiction.

Assume that all the leaf vertices are colored blue. Since the tree is connected, there must be at least one leaf vertex. Let's denote the number of red vertices as r and the number of blue vertices as b.

Since all leaf vertices are blue, the number of blue vertices (b) is greater than or equal to the number of red vertices (r). Therefore, we can write this as b ≥ r.

Now, let's consider the total number of vertices in the tree. Since each vertex is either red or blue, we can write the total number of vertices (n) as n = r + b.

Since the tree is connected, each edge connects two vertices. Therefore, the number of edges in the tree is n - 1.

Now, let's consider the sum of the degrees of all vertices in the tree. The degree of a vertex is the number of edges connected to it. Since each edge connects two vertices, the sum of the degrees of all vertices is twice the number of edges, which is 2(n - 1).

According to the Handshaking Lemma, the sum of the degrees of all vertices in a tree is equal to twice the number of edges. Therefore, we can write this as 2(n - 1) = 2n - 2.

Since each vertex is either red or blue, the sum of the degrees of all vertices is equal to the number of red vertices multiplied by the degree of a red vertex plus the number of blue vertices multiplied by the degree of a blue vertex. Mathematically, this can be written as 2(n - 1) = r * d_r + b * d_b, where d_r and d_b are the degrees of a red vertex and a blue vertex, respectively.

Since adjacent vertices have different colors, the degree of a red vertex (d_r) is equal to the number of blue vertices adjacent to it, and the degree of a blue vertex (d_b) is equal to the number of red vertices adjacent to it. Therefore, we can write this as 2(n - 1) = r * b + b * r = 2rb.

Simplifying this equation, we get n - 1 = rb.

Now, let's consider the inequality b ≥ r. If b = r, then n - 1 = r^2, which implies that r = sqrt(n - 1). Since n > 2, r is not an integer, which contradicts the assumption that r is the number of red vertices.

If b > r, then n - 1 > rb. Since n - 1 = rb, this implies that rb > rb, which is a contradiction.

Therefore, our assumption that all the leaf vertices are colored blue is false. Hence, there must be at least one leaf vertex colored red.

Therefore, we have proved that in a tree where adjacent vertices have different colors and there are at least as many red vertices as blue vertices, at least one of the leaf vertices is colored red.