Edge querying in graph theory

In this post, I will present three graph theory problems in increasing difficulty, each with a common theme that one would determine a property of an edge in a complete graph through repeated iterations, and seek to achieve a greater objective.

ESPR Summer Program Application: Alice and Bob play the following game on a $K_n$ ($n\ge 3$): initially all edges are uncolored, and each turn, Alice chooses an uncolored edge then Bob chooses to color it red or blue. The game ends when any vertex is adjacent to $n-1$ red edges, or when every edge is colored; Bob wins if and only if both condition holds at that time. Devise a winning strategy for Bob.

This is more of a warm-up to the post, since it has a different flavor from the other two problems, and isn't as demanding in terms of experience with combinatorics. However, do note that when this problem was first presented, applicants did not know the winner ahead of time; it would be difficult to believe that Bob can hold such a strong condition, especially when Alice seemingly had far more control over the structure of the game, and there are lots of traps that could led to a possible false solution.

Say that a "bad" vertex is one that is connected to some blue edge, and a "good" vertex is one that isn't. To solve this problem, I found it motivating to first think about what could lead to a win for Alice, when Bob has no proper choice. The most blatant examples would be things that happen towards the end of the game. For example, if only one good vertex remains but there are uncolored edges not adjacent to it, Bob would lose, since Alice can just query every edge adjacent to it, and Bob ends up either having no good vertices, or ending the game prematurely. 

This idea can be further generalized; if there is at least one edge between bad vertices that remains uncolored, Alice wins since she can simply query every edge that's adjacent to at least one good vertex. If the game doesn't end by the end of all of Alice's queries, there would be no good vertices left and Bob has no way of winning. Hence, Bob must adhere to a very strict strategy of always keeping every edge between bad vertices colored, and from this we can actually deduce the solution.

Solution: Bob marks the first edge blue. Then, on each query:

If Alice queries an edge between two good vertices, Bob can simply mark it red.

If Alice queries an edge between a good vertex and a bad vertex, Bob would mark it red, unless doing so makes the good vertex connected to every bad vertex and doesn't lead to winning. Then, Bob colors it blue. Note that at any point, Alice cannot query an edge between two bad vertices. Hence, Bob can definitely win when he has only one good vertex remaining.

(EDIT: this problem is nearly identical to IOI 2014, Task 3.)

The below two problems feature some form of optimization.

Canada/USA Mathcamp Application: You are investigating a dangerous cult, with the goal of uncovering its reclusive Mastermind. From previously gathered intelligence, you know that the cult has $n\ge 5$ members: the Mastermind, the Go-between, the Figurehead, and $n-3$ Pawns. Each member of the cult associates with some, but not all, of the other members. In particular:

• The Mastermind is very reclusive; they associate with the Go-between, but no other member.
• The Go-between associates with the Mastermind and the Figurehead, but none of the Pawns.
• The Figurehead associates with everyone except the Mastermind.
• The Pawns associate with the Figurehead, but not the Mastermind nor the Go-between. Some pairs of Pawns may also associate with each other (so, each Pawn could potentially have up to 97 total associations).

You cannot figure out which members have special roles just by looking. However, each day, you can select a pair of members to investigate, and determine whether they associate with each other. Find a strategy to find the mastermind in under $2n$ days.

The staff members of MathCamp presented a solution in $3n+\theta(1)$ time during a math jam. However, that can be further optimized.

The main observation is that: we can immediately (almost) determine the type of an individual if we query the edges between them and everyone else, from which we can keep track of two stacks of people, those who might be masterminds and those who aren't. The figurehead would be among the people who aren't masterminds, assuming that we didn't choose a special individual at the start, and the only person in the other stack who can't connect to the figurehead is the mastermind.

The full solution is as below: we can first ask the connection between a fixed member "Bob" and everyone else.

If there are $n-2$ positives or $1$ positive, we can immediately determine the Mastermind.

If there are $3\le m\le n-3$ positives, we know that Bob is a pawn. We can keep a stack $s_1$ of the members connected to Bob and another $s_2$ of the members not connected to Bob. Obviously, $s_2$ contains the mastermind and $s_1$ contains the figurehead, who only fails to connect to the mastermind. Hence, we can keep asking for the interaction between the top member in $s_1$ and the top member in $s_2$; when the stack becomes empty, the mastermind tops $s_2$.

If there are $2$ positives, it can't be known if Bob is a pawn or the go-between. However, we can then ask for the connection between the two that Bob has a positive connection with; if they connect, then Bob is a pawn and we can proceed as before. If they don't, then Bob is the in-between, and every other person who Bob can't connect to is a pawn; if Alice is someone Bob connects to, we can try to connect Alice with any pawn. Alice is the mastermind if and only if the result is negative.

This can be shown to take at most $2n-3$ days if we also use the process of elimination.

Side note: despite this solution, I was still rejected at the program :(

Alright, we'll move onto the final entry.

ISL 2019 C8: Alice has a $K_n$, where each edge has a direction that's not initially known to her. Each day, she can asks for the direction of one edge. Find a way to, after $4n$ days, determine whether there exists an edge with outdegree at most $1$.

The first non-trivial barrier is to come up with an $O(n)$ algorithm, which is simple enough for something near the end of the IMO Shortlist.

It's fairly easy to make all but one vertex have out-degree $1$ by simply building a spanning tree, where a vertex is "left alone" once it has an outgoing edge. Then, we can fully eliminate most of them in the same way, down to possibly at most $2$ (if two vertices with outdegree $1$ remain, and the edge between them was already drawn). This achieves a bound of approximately $5n$ queries pretty easily by simply brute-forcing the remaining $3$ candidates. 

However, that's not quite what we want. To optimize this solution further, say that after the initial two steps, vertices $a,b$ have one outgoing edge and $c$ has no outgoing edges. Suppose that the edge between $a,b$ was drawn during the first stage; neither of them were the final vertex added to the spanning tree while $c$ was, so for the tree to be acyclic, the edges $ac$ and $bc$ cannot have been drawn. After drawing these two edges, we can eliminate one of $a,b,c$ to come up with a solution that achieves the desired bound.