I was inventing a problem for a math contest, I was really pleased with it, but then I found a mistake in my solution and have not been able to solve it. It is as follows:

Alice and Bob play a game. Let $n$ be a fixed positive integer. Alice selects a connected simple graph on $n$ vertices. After this Alice and Bob take turns selecting a vertex with at least $1$ adjacent edge and removing all the edges adjacent to it. Bob starts. For which values of $n$ does Bob always have a strategy that allows him to take strictly more edges than Alice?

I have found it is possible for $n=2,3,5$ and that it is not possible for $n=1$ and every even integer above $2$ (Alice can select $K_{2,n-2}$). It remains to be seen if there is a non-trivial graph on an odd number of vertices that works.

Some trivial observations:

Bob can always take the graph with the highest degree every turn. For a graph to be able to resist this strategy it must have at least two vertices with the highest possible degree which are non-adjacent; the graph must also have an even number of edges.

We can also define $B(G)$ as the maximum possible difference between the number of edges for Bob and Alice that Bob can guarantee. We are then looking for graphs with $B(G)=0$. It is clear $B(G)=\max(d(v)-B(G - v))$, where $v$ is any vertex in $G$ and $d(v)$ is the degree of $v$.

  • $\begingroup$ It's not immediately clear to me that the greedy strategy (pick the highest-degree vertex) works. Let $G$ have a central vertex $v$ with high even degree; each edge from $v$ connects to a copy of some graph $H$. If Bob plays $v$, the resulting game has value zero (it's the direct sum of an even number of copies of $H$). How do I know there's no better strategy for Bob? $\endgroup$ – Tad Mar 13 '16 at 3:26
  • $\begingroup$ Greedy works for Bob un some graphs. $\endgroup$ – Jorge Fernández-Hidalgo Mar 13 '16 at 7:07

First, a solution for odd $n \ge 11$. For such $n$, there are graphs with $B(\cdot)=0$ (so Alice can pick them and prevent Bob from getting more edges).

This is the graph for $n = 11$. For greater odd $n$, add pairs of vertices that are connected only to J and K (and not each other).

Graph with vertices ABCDEFGHIJ and edges AB, BC, CD, EF, FG, HI, JB, JC, JF, JH, KB, KC, KF, KH

This was inspired by using the same graph on just the vertices ABCDEFGHI (which is not connected, so not a solution itself). On this reduced graph, it is easier to see that $B(\cdot) = 0$. There are three moves (B, C, F) that give two edges, but moves B and C are mutually exclusive (in terms of giving two edges).

J and K are added to make the graph connected. Alice can still break even because if Bob plays J or K, Alice can respond by taking the other of J, K (since these will always be equivalent moves), otherwise, Alice can pretend the graph is the reduced one. (A bit of care has to be taken because because the addition of J and K can cause adjacent vertices to last longer than they would in the reduced graph, but the graph is designed so that moves that would cause this to happen are bad moves.)

Alice's strategy on 13 or more vertices is the same, but if Bob takes one of the new vertices, Alice can respond by doing the same.

(I have attempted to computer-verify that this graph works for small values of $n$, and assuming my computer code is correct, the verification succeeds.)

For $n=7$, I found this graph via computer search:

Graph with vertices ABCDEFG and edges AB, BC, DE, EF, AD, BE, AG, DG

I found this graph more difficult to generalize than my $n=11$ example, but I did extend it to a graph with $n=9$ which appears to work:

Graph with vertices ABCDEFGHI and edges AB, BC, DE, EF, AD, BE, AG, DG, AH, BH, DH, EH, AI, BI, DI, EI

Following are some additional comments on the problem which OP has probably already noticed, but I think are worth mentioning:

First, $B(\cdot)\ge0$ always. This is because Bob can play a greedy strategy to ensure at least breaking even. From this it is also clear that Alice must always at least match Bob's score after each move if she wants to break even, otherwise Bob can resort to the greedy strategy to win.

Second, the greedy strategy is not always optimal. A good example is $K_{2,n-2}$ for odd $n$. Here, Bob can choose the non-greedy option and reduce the graph to $K_{2,n-3}$, which, as OP has already claimed, has $B(\cdot)=0$. Moreover, by a similar argument, adding a single vertex and adjacent edges to a graph with $B(\cdot)=0$ will never have $B(\cdot)=0$.

  • $\begingroup$ Thank you very much for answering, I think it works. I'll accept after I get some time to think it over. $\endgroup$ – Jorge Fernández-Hidalgo Oct 6 '16 at 14:10
  • $\begingroup$ Seems legit.${}{}$ $\endgroup$ – Jorge Fernández-Hidalgo Jun 15 '17 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.