Scores of black and white marks

We have a connected (undirected) graph with $n$ vertices, and $b$ black and $w$ white marks with $b+w=n$ and $\max(b,w)\geq 2$. In a placement of the marks on the vertices, the "score" of a mark is the ratio of its neighbors of the same color to its total neighbors (this ratio is always well-defined due to connectivity). A placement is called "nice" if it is not possible to rearrange the marks so that every mark gets a better or same score as before, and at least one mark gets a better score.

Is it true that in any nice placement, the sum of the scores is at least $1$?

The score may be $1$, if the graph is a triangle and $b=2,w=1$.

Solution 1:

The statement is true.

Let $G$ be our graph, $\{v_1, v_2, \dots, v_n\}$ be its vertices, and $(d_1, d_2, \dots, d_n)$ be the corresponding sequence of their degrees. Any placement $p$ of $b$ black and $w$ white marks also induces the corresponding sequence $(p_1, p_2, \dots, p_n)$, where $p_i$ is the number of vertices adjacent to $v_i$ and having the same color as $v_i$.

Definition 1. We say that a placement $q$ majorizes $p$, if it contains the same numbers of black and white marks as $p$ and induces the sequence $(q_1, q_2, \dots, q_n)$, where $\forall i \colon q_i \ge p_i$ and $q_i > p_i$ for at least one $i$.

The statement in question is equivalent to the claim that if

$$\frac {p_1}{d_1} + \frac {p_2}{d_2} + \dots + \frac {p_n}{d_n} < 1\,, \tag{1}$$

then there is a placement $q$ that majorizes $p$.

To prove it, first note that $(1)$ implies $\min(b,w) \ge 1$, otherwise every summand at the left-hand side of $(1)$ would be $1$ and the sum would be the natural number $n$. This also means that

$$n = b + w = \min(b, w) + \max(b, w) \ge 1 + 2 = 3\,. \tag{2}$$

Consider the spanning subgraph $H$ of $G$ that contains only edges connecting equally colored (by $p$) vertices of $G$. It breaks down into several connected components (whereas $G$ was connected). Note that each component contains only vertices of one color. We number the black components: $\mathcal B = \{B_1, B_2, \dots, B_t\}$. If $b_i = |B_i|$ are their sizes (in set theory terms), then $b_1 + b_2 + \dots + b_t = b$. Also do the same for the white components: $\mathcal W = \{W_1, W_2, \dots, W_s\}$. If $w_i = |W_i|$, then $w_1 + w_2 + \dots + w_s = w$. Let $k = t + s$ be the total number of components and $e$ be the total number of edges in $H$. Since a component with $r$ vertices contains at least $r - 1$ edges, summing this for all components, we obtain: $e \ge n - k$. On the other hand, $2e = p_1 + p_2 + \dots + p_n$. Since each $d_i \le n - 1$, from $(1)$ we have: $\frac {2e}{n - 1} = \sum_{i=1}^n \frac {p_i}{n - 1} \le \sum_{i=1}^n \frac {p_i}{d_i} < 1$, thus $2e < n - 1,$ $2n - 2k \le 2e \le n - 2$ and $$n \le 2k - 2\,. \tag{3}$$

Note that $k$ is the quantity of the numbers $b_i, w_i$ and $n$ is their sum. Thus $(3)$, in particular, implies that their average $\frac n k$ is less than $2$. Therefore, at least one of them is $1$. WLOG, $b_1 = 1$. Let $u \ge 1$ be the total number of units among $b_i$. The remaining $t - u$ numbers are $2$ or greater, hence $b = b_1 + b_2 + \dots + b_t \ge u + 2(t - u) = 2t - u$. Let $m = \min (w_1, w_2, \dots, w_s)$. Then $w = w_1 + w_2 + \dots + w_s \ge ms$. From this and $(3)$: $2(t + s) - 2 \ge b + w \ge (2t - u) + ms$, thus $u - 2 \ge (m - 2)s$. We conclude that the case $m > u$ is impossible since then $m - 2 > u - 2 \ge (m - 2)s$ and $0 > (m - 2)(s - 1)$, but $m \ge u + 1 \ge 2$ and $s \ge 1$. Therefore,

$$u \ge m\,. \tag{4}$$

The key part of the upcoming reasoning is based on the following definition and lemma.

Definition 2. A placement $p$ is called sub-balanced if there are two sets, $\mathcal B\,' \subseteq \mathcal B$ and $\mathcal W\,' \subseteq \mathcal W$ such that $\mathcal B\,' \cup \mathcal W\,'$ is a proper nonempty subset of $\mathcal B \cup \mathcal W$ and the total number of vertices in components from $\mathcal B\,'$ is equal to the total number of vertices in components from $\mathcal W\,'$.

Lemma. If $p$ is sub-balanced, then it isn't nice, i.e. there is another placement that majorizes it.

Proof. Let $p$ be sub-balanced. Denote by $V$ the set of all vertices contained in components from $\mathcal B\,' \cup \mathcal W\,'$. We compose the placement $q$ by simply changing colors of all vertices in $V$, i.e. from black to white in $\mathcal B\,'$ and from white to black in $\mathcal W\,'$. The ratio of black and white vertices remains unchanged. If $v_i$ was in some component $B_j$ or $W_j$, then all vertices counted by $p_i$ were in the same component. Its color may have changed, but all these vertices still have the same color in $q$, therefore $\forall i \colon q_i \ge p_i$. To prove that $q_i > p_i$ for some $i$, take two vertices, one of which is from $V$ and the other is not (this is possible because $V$ is a proper nonempty subset of $G$'s vertices). $G$ is connected, therefore we can connect these vertices by a path in $G$. There is an edge $(v_i, v_j)$ in this path such that $v_i \in V$ and $v_j \notin V\!.$ $v_i$ and $v_j$ were of different colors in $p$ because otherwise $v_j$ should have been in the same component as $v_i$ and therefore should have belonged to $V$. But now, as long as the color of $v_i$ has changed and the color of $v_j$ has not, $v_i$ and $v_j$ have the same color; hence $q_i > p_i$ and $q_j > p_j$. ∎

From this point on, we simply apply the lemma for the cases when $p$ is sub-balanced and exclude these cases from consideration. The first of such cases is $u > m$ — we take the white component of size $m$ as $\mathcal W\,'$ and $m$ black components of size $1$ as $\mathcal B\,'$; since $u > m$, there are still components remaining. The second case is $(u = m) \land ((t > u) \lor (s > 1))$ — we do the same to prove that $p$ is sub-balanced.

From $(4)$ it follows that the only remaining case is $u = m = t$, $s = 1$, i.e. $\mathcal W$ is a sole white component of size $t$, and $\mathcal B$ is a set of $t$ black components of size $1$. From $(2)$ it follows that $t > 1$. Let's prove that $t \le 3$. For this, we estimate the left-hand side of $(1)$ from below. The $t$ terms corresponding to black points are of no interest to us because $p_i = 0$ for them. Let $I$ be the set of the white vertex indices, $|I| = t$. For any $i \in I$, the difference $d_i - p_i$ is the number of black vertices adjacent to $v_i$ in $G$. It is at most $t$. Thus, $d_i = (d_i - p_i) + p_i \le t + p_i$ and $\frac {p_i}{d_i} \ge \frac {p_i}{t + p_i} = 1 - \frac t{t + p_i}$. Summing this for all $i \in I$ and using $(1)$, we get: $1 > t \left(1 - \sum_{i \in I} \frac 1{t + p_i}\right)$, hence

$$\sum_{i\,\in\,I} \frac 1{t + p_i} > \frac {t - 1}t\,. \tag{5}$$

$W_1$ is connected in $H$, therefore $\forall i \in I \colon p_i \ge 1$. Let's prove that $p_i > 1$ for at most one $i$. Indeed, otherwise $\frac {t-2}{t+1} + \frac 2{t+2} \ge \sum_{i \in I} \frac 1{t + p_i} > \frac {t - 1} t$ and we would get: $(t^3 - 4t) + (2t^2 + 2t)> t^3 + 2t^2 - t - 2$ and $2 > t$, whereas $t > 1$.

Now we know the structure of $W_1$, the subgraph induced in $G$ by the set of all white vertices: it is a star with $t$ vertices. If $t > 2$, and $v_i$ is its internal node, then $p_i = t - 1$ and $(5)$ turns into $\frac {t-1}{t+1} + \frac 1 {2t-1} > \frac {t-1}t$. From this, we conclude: $(2t^3 - 3t^2 + t) + (t^2 + t) > 2t^3 - t^2 - 2t + 1$, hence $3 > (t - 2)^2$ and $t = 3$.

What remains is to analyze 4-vertex and 6-vertex graphs of the designated structure. Note that each white vertex in them is adjacent to at least one black vertex because otherwise $d_i = p_i$ for some $i \in I$, which would contradict $(1)$. Moreover, at least one of the two white vertices for which $p_i = 1$, is adjacent to at least two black vertices because otherwise we would have two $\frac 1 2$ at the left-hand side of $(1)$. Let $x$ be such a vertex, $y$ be its white neighbour, and $z$ be a black neighbour of $y$. Since $x$ is adjacent to at least one black vertex different from $z$, we can swap the colors of $x$ and $z$ and obtain a placement that majorizes $p$. This concludes the proof.