# Homework Help: [Discrete math] Finding simple, nonisomorphic graphs with 4 nodes

1. Nov 9, 2013

### smithisize

1. The problem statement, all variables and given/known data
Draw all nonisomorphic, simple graphs with four nodes. (Hint: There are eleven such graphs!)

2. Relevant equations

N/A

3. The attempt at a solution

Well if you can imagine a square with the nodes as the vertices and no arcs connecting them, I figure that's isomorphic because there's no way for the bijection to 'order' the mapped nodes.
The solution to the problem is here:http://www.math.washington.edu/~dumitriu/sol_hw4.pdf
But I don't understand it. Why is their second solution a solution? Because I would think that if that is a solution, certainly the same, just with a diagonal instead of a top connector, would be a solution but it's not.

Please help me understand the process I have to go through to find these graphs on my own.
Thanks

Smith

2. Nov 9, 2013

### haruspex

Nonisomorphic here simply means don't count what is really the same graph twice. A graph in isolation cannot be said to be isomorphic or not. It is isomorphic or otherwise to some other graph. E.g. the two graphs you describe - the second in the solution and one consisting of just a diagonal - are isomorphic to each other, so you don't count both. They're isomorphic because there is a way of shuffling the vertices around that turns one graph into the other.