# Math Help - Graphs....up to isomorphism.

1. ## Graphs....up to isomorphism.

If $|V(G)|=n$. How many non-isomorphic graphs are there? In total, there are $\frac{n(n-1)}{2}$ edges but not all compose non-isomorphic graphs. For example, $G=(\{v_1,v_2,v_3\},\{v_1v_2\})$ and $G=(\{v_1,v_2,v_3\},\{v_1v_3\})$ but they are isomorphic.

2. There is quite a good discussion of the problem in the first chapter of the text, GRAPHS: An Introductory Approach by Wilson & Watkins. (Because of your location, you can find it in most mathematics libraries.) It turns out that the problem is different for labeled graphs than for unlabeled graphs. You seem to be using labeled graphs, graphs having named vertices . For unlabeled graphs Polya solve the problem in 1935. Wilson & Watkins give what they call “graph cards” at the end of chapter 1: they list all non-isomorphic unlabeled graphs of order 1 to 6. There are 153 non-isomorphic unlabeled graphs of order 6.

3. I was considering another way to kill this problem. Perhaps, we should consider the non-isomorphic adjancey matricies for n vertices?