On a social network, no user has more than ten friends ( the state "friendship" is symmetrical). The network is connected: if, upon learning interesting news a user starts sending it to its friends, and these friends to their own friends and so on, then at the end, all users hear about the news. Prove that the network administration can divide users into groups so that the following conditions are met: each user is in exactly one group each group is connected in the above sense one of the groups contains from $1$ to $100$ members and the remaining from $100$ to $900$.
Problem
Source: Saint Petersburg MO 2020 Grade 10 Problem 6
Tags: combinatorics
math_pi_rate
07.05.2020 23:58
Is something missing here? What if the social network simply consists of isolated users? @below, are you talking about the second line. However, there the problem simply defines what it means for a network to be connected. It doesn't say that the network is itself connected.
RagvaloD
08.05.2020 21:41
From second condition follows, that social network is connected graph, so don`t contain isolated users.
dgrozev
10.05.2020 09:35
So, we have a connected graph $G$ and have to partition its vertices into groups with corresponding sizes inducing connected subgraphs. Let $T$ be a spanning tree of $G$. Then, $\deg_T(v)\le 10$ for every vertex of $T$. Suppose $u_0$ is a root of $T$ and denote by $V(v)$ the number of vertices of the the subtree of $T$ consisting of $v$ and all vertices of $T$ upper than $v$. Taking a leef and proceeding down to $u_0$ let $v_0$ be the first vertex with $V(v_0)>900$. Then $v_0$ is connected with at most $9$ upward vertices $v_i,i=1,2,\dots 9$. If $V(v_i)\leq 900$ for all $i\in[1..9]$ we are done since $V(v_i)\in[100,900]$ for some $i$. Otherwise we go up until we reach a vertex $v_0$ with $V(v_i)\leq 900$ for all vertices upper than $v_0$. Removing one by one subtrees with vertices from $100$ to $900$ and taking care at the end, we can reach the goal.