Picture a city in which every house is occupied, every person has a network of friends, and roads connect some pairs of houses but not others. A swap is allowed only when both tests pass: the two people are friends, and their current homes are joined by a road. Now ask the unnerving question: starting from one arrangement, can you reach every other arrangement without ever breaking those rules?
This is not just a parlor puzzle. It is a mathematical way to study constrained swaps, including sliding puzzles such as the 15-puzzle. In the broader version, one graph records friendships and another records roads. Each possible arrangement is a point in a vast map of states; a legal swap draws a path from one point to another. With n people and houses, that map contains n factorial possible arrangements. Finding a route by checking them one at a time quickly becomes hopeless.
The catch is that an obvious swap may be forbidden. Two friends might be sitting in houses with no road between them. Yet perhaps one can move other people around, briefly rearrange the city, and bring the original pair together under better conditions. The hard part is proving that such detours always exist—not for one clever arrangement, but for every arrangement in an entire class of networks.
In a paper submitted to arXiv on October 12, 2026, Kai Mawhinney resolves a conjecture about when that guarantee holds. The rule is expressed using each network’s minimum degree: the number of connections belonging to its least-connected person or house. If both networks are connected, and twice the smaller minimum degree plus three times the larger is at least three times the number of people, then every arrangement can be reached from every other by legal swaps.
The surprising hinge is local. Mawhinney shows that, under this condition, any two people who are friends can trade places in a bounded number of legal moves—even when their homes do not have a road between them at the start. The bound is an absolute constant: it does not grow as the city gets larger. Once neighboring friends can reliably exchange positions, longer routes through the friendship network let the proof build up arbitrary rearrangements.
How can a theorem promise a detour without listing every possible route? The proof zooms in on the houses occupied by one person’s friends. Because the networks have enough connections, this neighborhood cannot be too sparse. Its road pattern is forced into a small set of structures: it may hold together robustly, split into two dense pieces, or have a narrow bottleneck whose removal separates it. Each shape suggests a different way to stage swaps, using nearby friends and houses as temporary stepping-stones.
This is where the investigation gets delicate. A bottleneck can make an apparent route fail; a direct move can be unavailable in one arrangement and available in another. The proof repeatedly changes the arrangement to expose a usable path, then shows that the necessary local structure cannot remain blocked under the degree condition. Some special low-degree cases are handled separately, while the general argument combines neighborhood counts with careful structural casework. It is not a universal recipe for the shortest route, but a proof that a route of controlled length exists.
The result also says something about the cost of getting there. The paper bounds the diameter of the arrangement map—the longest shortest route between any two arrangements—by a quantity on the order of the square of the number of people divided by the smaller minimum degree. That scale is sharp in general: Mawhinney constructs examples where routes really can be that long. But when both minimum degrees grow in proportion to the city’s size, the longest necessary route is only on the order of the number of people.
The boundary matters as much as the guarantee. The theorem gives a sufficient condition, not a complete answer for every pair of networks. The paper also constructs disconnected arrangement maps outside the guaranteed region, including examples built from blocks of people whose connection patterns in the two networks complement each other. Starting from a natural arrangement, no legal swap can carry anyone across certain block boundaries. Lots of connections, by themselves, do not erase every trap.
That leaves a map with unexplored territory: a band of degree combinations where it is not yet known whether every arrangement is reachable or whether some hidden partition can keep the state space split. Filling in that region could turn a strong rule of thumb into a sharper classification of constrained swapping puzzles. The price of this advance is clear: the guarantee needs substantial network structure, and minimum degree alone has not yet revealed the whole story. The next frontier is to find what the gaps know that the degrees do not.
