The friends and strangers graph is a mathematical construction built from two graphs X and Y, each having the same number of vertices. Imagine placing one graph on top of the other, with a permutation telling you how to match up the vertices. Two such matchings are considered neighbors if you can get from one to the other by swapping just two elements that are connected in both graphs simultaneously. The resulting object, called the friends and strangers graph, captures all the ways you can rearrange one graph relative to the other through these local swaps. A central question is when this graph is connected, meaning whether you can reach any arrangement from any other through a sequence of valid swaps.
A key factor governing connectivity turns out to be the minimum degree of X and Y, which measures how well-connected each graph is internally. Researchers had conjectured that if the minimum degrees of X and Y are large enough relative to the number of vertices, specifically satisfying a certain weighted inequality, then the friends and strangers graph is always connected. This paper proves that conjecture. The core insight is showing that whenever two vertices are neighbors in X, they can swap their positions in the arrangement in a bounded number of moves, no matter what configuration you start in. This local swapping capability, bounded by an absolute constant, is the engine that drives the global connectivity result.
Beyond just proving connectivity, the paper pins down how large the diameter of the friends and strangers graph can be, meaning the worst-case number of steps needed to get from one arrangement to another. The authors show the diameter grows at most like the square of the number of vertices divided by the minimum degree, and that this bound cannot be substantially improved. This sharpens earlier results and answers several open questions. They also show that even when X and Y are not themselves connected, the same degree condition forces any connected piece of the friends and strangers graph to have diameter at most proportional to the square of the number of vertices.