Bipartite Graphs/Complete Bipartite graphs

[kiley1018]

Just a couple of questions and really do not make sense to me.

I know what a bipartite graph is and a complete bipartite graph is but

1. Which complete bipartite graphs have euler circuits? Is this when only bipartite graphs that have an even number of vertices on each side??

2. Are any circuits bipartite (but not complete bipartite) graphs? Is this when there are odd and even number of vertices on each side?

 

[pka]

1. Which complete bipartite graphs have Euler circuits? Is this when only bipartite graphs that have an even number of vertices on each side??

2. Are any circuits bipartite (but not complete bipartite) graphs? Is this when there are odd and even number of vertices on each side?

For #1, we have an Euler circuit on if each vertex is even. So what does that mean with respect to the two sets of vertices?

For #2, what about a simple rectangle with no diagonals?

 

[kiley1018]

Ok, A bipartite graph is a graph that has two sets of vertices. Think of it as if you color these vertices. One set of vertices are red and the other set is blue. So you have 4 red vertices and 3 blud vertices. A bipartite graph will have edges to go from blue to red and red to blue but NO edges will connect to the same color vertices.

Euler circuts have even degrees in each vertices but if there are four red and three blue you will have four edges in the blue vertices but only three in the red vertices.

So you must only be able to have an euler circuit if you have an even number of vertices in each set. These graphs are written K4,3. Four for the red vertices and three for the blue vertices. Is this correct?

2. Are any circuits bipartite but not complete bipartite? To have a circuit you need to at least have 2 degrees in each vertices. So you could not have a circuit because you would have to double back on edges unless you have a complete bipartite graph becuase you need enough edges to go back and forth to get to the end and then back up to where you began. Does this make sense?

I dont know if I am on the right track or not?

 

[pka]

Look, you are making #2 far to complicated.
A simple rectangle with no diagonals is a circuit and a bipartite graph.

 

[kiley1018]

Is there a way you can draw a picture of this simple rectangle. i am just not seeing it in my mind. I need a visual.

 

[pka]

Is there a way you can draw a picture of this simple rectangle.

The point of the rectangle suggestion was to get you to think. The rectangle is an example of a circuit and a bipartite graph. But it is complete. However a hexagon is circuit and a non-complete bipartite graph.

 

[kiley1018]

Oh my gosh, i totally understand. I have a hard time thinking outside the box. I was always thinking that the colors had to be on the same side, not that you could have them opposite or anything like that.

Thanks so much, You have been a great help