The friends-and-strangers graph 
of simple graphs 
and 
on 
vertices is the graph whose vertices
are all bijections 
. Two such bijections 
and 
are adjacent when 
for an edge 
of 
such that 
is an edge of 
. Thus 
has 
vertices, and its edges
represent friendly swaps (Defant and Kravitz 2021).
Equivalently, the vertices of 
are positions, the vertices of
are people, and edges of 
indicate friendship. A move swaps two friends occupying adjacent positions. This interpretation includes
sliding puzzles: the 15 puzzle is represented by taking
to be the 
grid graph and 
to be the star graph whose center
represents the empty cell. Inversion of bijections
gives the graph isomorphism 
.
Krishnan and Li (2026) proved that, for connected 
and 
,
the vertex connectivity of 
equals its minimum
vertex degree. They also proved that the vertex
connectivity of each connected component
of 
equals its minimum vertex degree.
For connected 
and 
on 
vertices, Mawhinney (2026)
proved that
 |
implies that 
is connected, where
denotes minimum vertex degree. Under the
same hypothesis its graph diameter is 
, using big-O
notation. The order of this upper bound is sharp in the worst case, not necessarily
for every pair 
.
