1. Not finding help here? Sign up for a free 30min 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!

[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

    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. jcsd
  3. Nov 9, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: [Discrete math] Finding simple, nonisomorphic graphs with 4 nodes
Loading...