A combinatorial design has six varieties {1, 2, 3, 4, 5, 6}, and nine blocks of size 2. Every variety occurs in three blocks, and the design is simple. Prove that there are exactly two non-isomorphic ways to do this.
I was able to solve a similar problem which asked me to construct two non-isomorphic designs with three varieties and five blocks of size 2, and every possible pair of varieties occurring at least once.
How can I develop this one to solve the first quesion?
Notice that you are counting isomorphism classes of simple graphs on six vertices in which every vertex has degree three.
If there is a triangle in the graph, then one easily sees that the whole graph is
Indeed, no two triangles can share an edge, so that is the only possibility.
If there is no triangle, let $x$ be a vertex and let $a$, $b$, $c$ be its neighbors. No two of $a$, $b$, $c$ can be connected, because that would create a triangle. It follows that all three of them are connected to the other two vertices $u$ and $v$. That completely determines the graph, which is then