Results 1 to 7 of 7

Math Help - Making a bipartite graph with 12 vertices and each vertex degree must be great than 2

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Columbus
    Posts
    6

    Making a bipartite graph with 12 vertices and each vertex degree must be great than 2

    Hello everyone,


    I am pretty new to graph theory in general and was having quite a bit of trouble with this questions. This is just practice for myself after I've read a book describing the basics of graph theory. I was able to make other graphs to satisfy all kinds of conditions, but I am getting totally lost at this bipartite graph. I've tried a lot of different things and am at a loss at this point. I've went several ways and used up multiple sheets of paper trying to solve this and still cannot. Can anyone lend me a helping hand at this? I would very much appreciate it. The graph I am trying to make has to be bi partite, have 12 vertices, each having a degree of over 2, and be a Eulerian circuit and hamilton circuit.

    All in all I think graph theory is kind of nifty but I feel like it's a waste of time to keep drawing. Isn't there a sure fire method to making these graphs????

    Again, I appreciate any help at all!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Making a bipartite graph with 12 vertices and each vertex degree must be great th

    Quote Originally Posted by maverik877 View Post
    The graph I am trying to make has to be bi partite, have 12 vertices, each having a degree of over 2, and be a Eulerian circuit and hamilton circuit.
    What about K6,6? This PDF document contains some ideas.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    Columbus
    Posts
    6

    Re: Making a bipartite graph with 12 vertices and each vertex degree must be great th

    Does K6,6 mean 6 on one side and 6 on the other? This is what I've been trying to do since on and off today for about 7 hours. Thank you for your help, but The pdf is pretty much math definitions and that's that. I'm trying to get a pattern that I can read/find out. Like if I have (A,B,C,D,E,F) on one side and (G,H,I,J,K,L) on the other side. I'm trying to find a Eulerian pattern such that I can write down the pattern and if I gave it to someone that could trace it.

    Also, if all degrees are even, it is a Eulerian circuit? Also, am I able to have a self loop somewhere? Is that against any kind of rule?
    Last edited by maverik877; September 17th 2012 at 04:54 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Making a bipartite graph with 12 vertices and each vertex degree must be great th

    Quote Originally Posted by maverik877 View Post
    Does K6,6 mean 6 on one side and 6 on the other?
    Yes.

    Quote Originally Posted by maverik877 View Post
    The pdf is pretty much math definitions and that's that.
    Did you see problems 1(d) and (e)?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2012
    From
    Columbus
    Posts
    6

    Re: Making a bipartite graph with 12 vertices and each vertex degree must be great th

    Okay, I see. So I don't actually have to trace the whole god awful thing to find out if it's a Eulerian circuit because it all degrees from vertices are even( in my case over 2), then it IS a Euclerian?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Making a bipartite graph with 12 vertices and each vertex degree must be great th

    Quote Originally Posted by maverik877 View Post
    Okay, I see. So I don't actually have to trace the whole god awful thing to find out if it's a Eulerian circuit because it all degrees from vertices are even( in my case over 2), then it IS a Euclerian?
    Yes. See Wikipedia page about Eulerian cycles.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2012
    From
    Columbus
    Posts
    6

    Re: Making a bipartite graph with 12 vertices and each vertex degree must be great th

    Thank you very much for your help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: August 20th 2012, 07:05 AM
  2. Replies: 0
    Last Post: April 19th 2012, 11:32 AM
  3. Graph theory, bipartite Graph
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: March 10th 2012, 05:47 AM
  4. Bipartite Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 14th 2010, 02:37 AM
  5. Replies: 0
    Last Post: October 5th 2009, 05:54 PM

Search Tags


/mathhelpforum @mathhelpforum