We are given a graph $K_6$. How many pairwise non-isomorphic graphs can we get if we delete 3 edges?

Question

I am looking for help with the question above. Actually have no idea what the answer is and especially how to prove the answer. Any help is highly appreciated.

Answer 1

Subgraphs $G$ and $H$ are isomorphic iff their complements $K_6 \setminus G$ and $K_6 \setminus H$ are isomorphic. Now it is a matter of counting graphs with $6$ nodes and $3$ edges. The three edges can be in three different components, yielding $1$ subgraph $K_2 \cup K_2 \cup K_2$. The three edges can be in two different components, yielding the union of a path of length $2$ and $K_2$. The three edges can be in one component in $3$ different ways: a path of length $3$, a triangle $K_3$, or a star $K_{1,3}$. The total count is therefore $1+1+3=5$.

Answer 2

There are 5 non-isomorphic graphs with $6$ vertices and $12$ edges with adjacency list form as follows.

1: 1[4 5 6] 2[4 5 6] 3[4 5 6] 4[1 2 3 5 6] 5[1 2 3 4 6] 6[1 2 3 4 5]
2: 1[3 4 5 6] 2[4 5 6] 3[1 5 6] 4[1 2 5 6] 5[1 2 3 4 6] 6[1 2 3 4 5]
3: 1[3 4 5 6] 2[5 6] 3[1 4 5 6] 4[1 3 5 6] 5[1 2 3 4 6] 6[1 2 3 4 5]
4: 1[3 4 5 6] 2[3 4 5 6] 3[1 2 5 6] 4[1 2 6] 5[1 2 3 6] 6[1 2 3 4 5]
5: 1[3 4 5 6] 2[3 4 5 6] 3[1 2 5 6] 4[1 2 5 6] 5[1 2 3 4] 6[1 2 3 4]

I recommend nauty on the web for situations where graphs have few vertices or edges. Of course, the problem you are considering can be handled by hand.

Edits: Thanks RobPratt for informing me that my original answer was wrong.