Valid Graphs (Up To Isomorphism)

This page shows the 8 unique valid bipartite graphs for 5 agents and 5 pieces after quotienting by isomorphism. In the isomorphism action, a1 is fixed, while a2..a5 can be permuted and b1..b5 can be permuted.

Build: 2026-04-01 17:22:33

Critical Transition Definition

Starting from a graph, if we remove the critical edge (red) and add the appearing edge (green), and the resulting graph is valid, then the transition is not critical.

Validity Definition Used Here

Every agent a1..a5 has degree at least 1.
The graph has exactly 8 edges (2n-2 for n=5).
For every piece bj, at least one holds: (i) a1 is connected to bj, or (ii) bj is connected to at least two agents.
An agent is active if its degree is at least 2.
No piece bj is connected to a1 and also to another active agent at the same time.
If ai and aj are active and both are different from a1, then at most one piece is adjacent to both.