Thread: 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!!!

Originally Posted by maverik877

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 K_6,6? This PDF document contains some ideas.

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?

Originally Posted by maverik877

Does K6,6 mean 6 on one side and 6 on the other?

Yes.

Originally Posted by maverik877

The pdf is pretty much math definitions and that's that.

Did you see problems 1(d) and (e)?

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?

Originally Posted by maverik877

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.

Thank you very much for your help.