Consider the bipartite graph $G = (X, Y, E)$, with $|X| = |Y| = n$. We can think of $X$ and $Y$ as clusters of $n$ switches on either end of a long hallway.
Each switch on one end of the hallway has a wire connecting it to exactly one other switch on the other end of the hallway, so there are exactly $n$ wires and $G$ is $(1,1)$-biregular. Our goal is to discover this edge structure, which we do not know.
Each turn, we can choose any number of switches to be in the ON position. We then press a GO button, and a light will turn on if any edges can be formed by our set of ON switches.
For example, if I choose switches $\{1, 2, B\}$ to be in the ON position, the light will turn on since $2B$ is an edge. If I choose $\{1, 2, 4, C\}$ to be in the ON position, the light will remain off.
What's a good strategy to determine exactly which switch in $X$ maps to which switch in $Y$ in as few turns as possible?
(A simple strategy taking up to $n^2$ turns is to try every combination of one switch from $X$ and one switch from $Y$).
Variant 1: Suppose we know only that $G$ is bipartite ($|X|$ need not equal $|Y|$, and some switches can have multiple wires connecting to it or none at all).
Variant 2: Suppose $G$ is as in the original problem, but a turn is now defined by having to walk through the hallway. In between turns, we can flip switches, press GO, and observe the result as many times as we like, but can only modify switches from $X$ or from $Y$ depending on which end of the hallway we're currently at.
Variant 0
Clearly there are $n!$ possible configurations, which gives a trivial lower bound on the number of tries needed to distinguish all of them, since each try only gives $2$ cases. But like with comparison sorting, it is unlikely that we will ever be able to determine the optimal number of tries except for very small $n$. We can get to within a linear factor easily, since it is easy to determine which switch $1$ is connected to in $\lceil \log_2(n) \rceil$ tries, and then which switch $2$ is connected to in $\lceil \log_2(n-1) \rceil$ tries, and so on. I think that can be considered a good enough answer.
Variant 1
There are now $(2^n)^n$ possible configurations, and so it is obvious what the optimal algorithm is.
Variant 2
I don't know the answer. Certainly we need no more than $(n-1)$ walks, and I think it is optimal, but I don't see immediately how to prove it.