1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Nov 9, 2013 #1
    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


    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.

  2. jcsd
  3. Nov 9, 2013 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted