Let 
and 
be simple graphs on 
vertices. The friends-and-strangers
graph 
has as its vertices 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.
