Graph Theory Lessons

graphic graphic graphicLesson 9: 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 coloring 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. 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 and 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.
graphic
Fig. 12, Yet another picture of a cube, properly colored

  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. If in a bipartite graph G with V1 and V2 as above we have that every vertex in V1 is adjacent to every vertex in V2 then G is a complete bipartite graph. If V1 has r vertices and V2 has s vertices then the complete bipartite graph is written as Kr,s. To get a graph of K3,4 with your program choose Graph then Complete then Complete Bipartite and when it asks for the number of vertices on the left enter 3, and when it asks for the number of vertices on the right enter 4.
    graphic
    Fig. 13, The graph K3,4


    Note that figure 12 is a bipartite graph that is not a complet bipartite graph. The applet below shows more examples of complete bipartite graphs.


    applet 9

    Use the Petersen program to look at the statistics of a few complete bipartite graphs. Find a formula for the number of edges e in Kr,s.

  4. What is the maximum number of edges that a complete bipartite graph with a total of n vertices, i.e. r+s=n, could have? [Hint: you need to maximize the answer to problem 3].
  5. If a complete bipartite graph Kr,s is regular, what can you say about r and s?
  6. Which complete bipartite graph is trivalent?
  7. Look at the adjacency matrices of a few complete bipartite graphs and describe the pattern you observe.
  8. 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

    e-mail: C. Mawata
    graphic graphic graphic
    © C. Mawata