image Graph Theory Lessons image

rule

previous index next Lesson 16: Bipartite Graphs

A bipartite graph is a graph G whose vertex set V can be partitioned into two non empty sets V1 and V2 in such a way that every edge of G joins a vertex in V1 to a vertex in V2. An alternative way of thinking about it is that if you were to color the vertices in V1 one color and those in V2 another color then adjacent vertices would have different colors. A non-null graph is bipartite if and only if its chromatic number is 2. A null graph with more than one vertex is trivially bipartite as you can partition the vertex set any way you like.

Java Web Start Activity:
The Java Web Start application below will help you to understand bipartite graphs. Draw a graph in the same way as you have done in previous applications. If the graph non-null and bipartite it will be drawn so that one set of vertices is on the right and the other on the left. The graph will also be properly colored.

Java Web Start Application 16.1: Bipartite graphs

Petersen Activity:
In the last exercise you found that the cube has chromatic number 2. Get the graph of a cube again (it is under the Platonic Graph menu item) and after you get it select Properties | Bipartite?. The graph will be redrawn so that one set of vertices, V1, is on the left and the other, V2, is on the right.

Fig 16.1. The cube

  1. Which of the platonic graphs is bipartite?
  2. Is it possible for a bipartite graph to contain a triangle as a subgraph? Hint: What is the chromatic number of a triangle?
  3. A bipartite graph is used in a certain college to model the relationship between students and courses. Let the vertices in one part, (call it V1) represent the students and the vertices in the other part (call it V2) represent the courses. What do the following represent?
    • the degree of a vertex s in V1
    • the degree of a vertex c in V2
    • the fact that two vertices s1 and s2 in V1 are adjacent to the same vertex c in V2.

Answers


© C. Mawata