A Bulgarian Winter Competition, 2020. Part II

Problem 11.4. A connected graph $G$ with $N\ge 3$ vertices is given. For any cycle $v_1,v_2,\dots,v_m$ in $G$ there exist three vertices $v_i,v_j,v_k$ which also form a cycle. Two players $A,B$ play the following game. At first, $A$ enumerates the vertices of $G$ with distinct natural numbers from $1$ to $N$ . Then $B$ chooses two natural numbers $N>a>b\ge 1$ and places a white token in the vertex numbered as $a$ and a black token in the vertex numbered as $b$ . After that the players play in turn, starting from $B$ . At each move, $B$ marks some (possibly zero) of the vertices adjacent to the black token and moves the token to an adjacent vertex not yet marked and with a bigger number assigned. At each turn, $A$ moves the white token in an adjacent unmarked vertex. If it’s not possible, the token stays still.
$B$ wins if reaches the vertex numbered with $N$ before $A$ reaches $N$ or any vertex adjacent to $N$ .
Determine whether $B$ has a winning strategy.

Some comments and motivation. Taking the a complete graph as $G$ it easily follows $B$ cannot win in this particular case. So, the answer should be “NO”, $B$ doesn’t have a winning strategy. Apparently, it was not intended as an argument. But, for sure it rules out the possibility the answer were “Yes”. So, most probably, $B$ cannot win, no matter of the graph $G$ and we are expected to prove it.
I mean, the way the question as asked, implies the answer. But had the question been “Determine whether $A$ can always prevent $B$ from winning”, there would be no hint revealed, and the two possible cases – “No”, “Yes” need non-trivial argument.
Anyway, a nice problem!

As a motivation for the following solution, consider $G$ be a tree. Then $A$ can enumerate the vertices, starting from some root, an labeling downwards each level in some order. Thus, $B$ cannot place its token closer to the root than that of $A$ .
In case $G$ has a cycle, we can also construct a spanning tree (by breadth-first-search algorithm (BFS) to label each level by contiguous numbers, tagging the root by $N$ and enumerating downwards the levels. But, this time, there may be cross edges and $B$ could lock the vertices on the tree on the levels closer to the root and prevent $A$ from catching up with $B$ . But BFS algorithm as a bonus constructs a tree $T$ with a good property, often used. Any edge in of the graph that is not in $T$ is a cross edge between vertices either in the same level or in two consecutive levels of $T$ . This fact would allow us to control better the possible moves of the players between levels of the spanning tree. Playing with it by putting edges on the skeleton $T$ , it could be seen an additional effort is needed to enumerate the vertices on the same level in a way not allowing $B$ to hinder $A$ on her way to the root.

Solution.

The idea is to construct a spanning tree using the breadth-first-search algorithm, with an additional criterion of ordering the vertices at each level. We take a vertex $v_0$ and label it with $N$ . This is the level $L_0$ .

The spanning tree/enumeration algorithm. Suppose we have already labeled all vertices up to some level $L_k$ and proceed finding (and labeling at the same time) vetices in the next level $L_{k+1}$ , which is empty at that moment. We start from the vertex $v_1$ with the greatest label in $L_k$ . Assume we are at $v_i\in L_k,i\ge 1$ . We take the set $N_i$ of all neighbours of $v_i$ not already in the tree. We start the following subroutine.
$(*)$ Calculate for each $u\in N_i\setminus L_{k+1}$ the value

$f(u):=\displaystyle \sum_{v\in N(u)\cap (L_k\cup L_{k+1}) }2^{\ell(v)}$

where $\ell(v)$ is the label of $v$ and $N(u)$ is the set of all neighbours of $u$ in $G$ . Take the vertex $u$ with the maximal $f(u)$ , label it with the greatest label not yet used and put it into $L_{k+1}$ . Then again apply the subroutine $(*)$ till exhaust all vertices in $N_i$ .
After all vertices in $N_i$ has been labeled, we proceed to the next vertex in $L_k$ not yet processed and with the greatest label, till finally we have run through all vertices in $L_{k}$ and have filled and labeled the next level $L_{k+1}$ . Thus, we constructed and labeled a spanning tree $T$ $\square$

You see, it’s actually the breadth-first-search algorithm (BFS), but when finding the children of a vertex, we take care of labeling them appropriately, not just randomly. In fact that ordering is a lexicographic one, for a vertex $u$ we arrange $N(u)$ that are already labeled in decreasing order of their labels and choose a vertex with the maximal such string.
BFS guarantees the edges of $G$ not in $T$ can only be cross edges between vertices either in the same level or in two consecutive levels. Moreover a vertes $x\in L_k$ can only be connected with a vertex $y\in L_{k+1}$ which predecessor $x' \in L_k$ has a greater number than $x$ . It’s because $x'$ is processed before $x$ .

For briefness of explanation, visualize the tree $T$ as its root $v_0$ being at the top, its levels $L_0,L_1, \dots$ are placed top to bottom. At each level left to right are arranged the vertices with decreasing labels. We will prove at each move $A$ can place her token in the vertex with label not less than that of $B$ .

Initially, $B$ is at the same level or below $A$ . If $B$ is below $A$ , nothing can prevent $A$ from going up the tree till reaches $v_0$ . So, suppose $A,B$ are initially at the same level, say $L_{k}$ . By $\ell(A)$ resp. $\ell(B)$ we denote the label of the current position of $A$ , resp. $B$ . Note that if $B$ decides to go up, $A$ can do the same, because if $\ell(A)\ge \ell(B)$ there exists a neighbour of $A$ in the upper level, which isn’t marked/locked and with a greater or the same label as that of $B$ ‘s.
Actually, the only way $B$ can prevent $A$ from going up the tree is in case $N(A)\cap L_{k-1}=N(B)\cap L_{k-1}$ and $B$ decides to lock all her neighbours in $L_{k-1}$ and walk on the level $L_k$ . Let’s consider this case.

Suppose, $A$ jumps from a vertex $v_1\in L_k$ to a vertes $v_2\in L_k$ but with a greater label.
We claim

$N(v_1)\cap L_{k-1}\subset N(v_2)\cap L_{k-1}\quad (1)$ .

Indeed, assume there is a vertex $v_1'$ in $L_{k-1}$ which is a neighbour of $v_1$ but not of $v_2$ . Then there also exists a vertex $v_2'$ in $L_{k-1}$ which is a neighbour of $v_2$ but not of $v_1$ , since otherwise the label of $v_2$ would be less than that of $v_1$ . Consider the cycle $v_1v_2v_2'\dots v_0\dots v_1' v_1$ (from $v_2'$ we go up along the tree to $v_0$ and then down to $v_1'$ ). Since $v_1,v_2$ are not connected to levels upper than $L_{k-1}$ (property of BFS algorithm) and $v_1v_2', v_2v_1'$ are not edges, it contradicts with $G$ being a chordal graph. (here is the only place that property of $G$ is used).

Hence, $(1)$ is established. Now, $A$ jumps from $u_1$ to $u_2\in L_k\cap N(u_1)$ with the greatest label. Such one does exist, since otherwise $\ell(u_1)<\ell(v_1)$ . Moreover, $\ell(u_2)\geq \ell(v_2)$ with the same argument. The only case, $B$ can prevent $A$ from escaping to the uper level along the tree is again when $N(u_2)\cap L_{k-1}=N(v_2)\cap L_{k-1}$ due to $(1)$ and $\ell(u_2)\geq \ell(v_2)$ . In this case $B$ must lock again all vertices in $N(v_2)\cap L_{k-1}$ . Proceeding like that, either $A$ escapes on the upper level, on a vertex with a greater label than that of $B$ or both players move along the level $L_k$ till exhaust all their neighbours.