Problems

Age
Difficulty
Found: 4

Prove that there is a vertex in the tree from which exactly one edge emerges (such a vertex is called a hanging top).

A group of \(2n\) people were gathered together, of whom each person knew no less than \(n\) of the other people present. Prove that it is possible to select 4 people and seat them around a table so that each person sits next to people they know. (\(n \geq 2\))

Prove that the following facts are true for any graph:

a) The sum of degrees of all vertices is equal to twice the number of edges (and therefore it is even);

b) The number of vertices of odd degree is even.