There are several gentlemen in the meeting of the Diogenes Club, some of which are friends with each other (friendship is mutual). Let's name a participant unsociable if he has exactly one friend among those present at the meeting. By the club rules, the only friend of any unsociable member can leave the meeting (gentlemen leave the meeting one at a time). The purpose of the meeting is to achieve a situation in which that there are no friends left among the participants. Prove that if the goal is achievable, then the number of participants remaining at the meeting does not depend on who left and in what order.
Problem
Source: St Petersburg 2023 10.6
Tags: combinatorics, St. Petersburg MO, graph theory
16.08.2023 16:48
Let us interpret this process as operations on a graph. So, we have an initial graph and are allowed to sequentially delete vertices that are connected to a vertex of degree $1$. We must prove that acting like that it is impossible to be left with isolated vertices with different cardinalities. Consider the sequence of operations backwards. We start from an initial graph $G_0$ with $m$ isolated vertices. At $i$-th step, $i=1,2,\dots$ we are allowed to add to $G_{i-1}$ a new vertex $v$. We connect $v$ to some $v'\in V(G_0)$ that is still isolated in $G_{i-1}$. We also may connect $v$ to some subset (which may be empty) of vertices in $G_{i-1}$ thus obtaining a graph $G_i$. Let us refer to this operation as "adding a vertex $v$". We will prove that it's impossible to start with two sets of isolated vertices $G_0$ and $G'_0\,,\, |G_0|\neq |G'_0|$ and after a sequence of operations to obtain the same graph $G.$ That is, knowing that $G$ is obtained by a sequence of operations $$G_0\to G_1\to\dots\to G_k=G \qquad (1)$$we can recover $|G_0|$ uniquely. We will prove it by induction on the number of vertices in $G$ (on the complexity of $G$). It's trivial when $G$ consists of $1,2$ or $3$ vertices. Consider a graph $G$ with $n$ vertices for which a sequence like in $(1)$ does exist. Assume that we can recover the last operation in the sequence $(1)$, i.e. there exists only one vertex $v$ in $G$ that is connected to a vertex of degree $1$. In this case we remove $v$ and apply the induction hypothesis. Assume now there exist at least two vertices $v_1,v_2$ such that $v_1$ is connected to $v'_1,$ $v_2$ is connected to $v'_2$ and $d(v'_1)=d(v'_2)=1$. Apparently $v'_1\neq v'_2$. Here is a crucial observation. Suppose a vertex $v$ is connected to a vertex $v'$ in $G$ and $d(v')=1.$ It means, at some stage in $(1)$ there is an operation "adding a vertex $v$". Then we can "move" this operation at the final step and the result, i.e. the graph $G$, will be the same. So, we can assume that "adding a vertex $v_1$" and "adding a vertex $v_2$" are the last two operations. If we remove $v_1$ we get a graph with less vertices and by the induction hypothesis we can recover the number of vertices of its initial graph. The same is true if we remove $v_2$ first. We claim that the two obtained numbers are equal. Indeed, if they are not, and we remove both vertices $v_1,v_2$, we get a graph $G'$ and the cardinality of its initial state $G'_0$ would be equal to two different numbers, contradiction.