Graph Theory Lessons

1. The cube is the only platonic graph which is bipartite.

2. A bipartite graph does not contain any triangles since the chromatic number of a triangle is 3 while a bipartite graph has chromatic number 2.

3. The number of edges in K_r,sis rs.

4. We need to maximize e = rs. Since r + s = n, we can write e = r(n - r). Note that the graph of e against r is a parabola with intercepts 0 and n on the horizontal (r) axis, and a maximum when r = n/2. Now r has to be an integer so this requires n to be even.The maximum value of e is ( n/2 )².

   If n is odd, then the maximum will ocurr when r is as close to n/2 as posible, i.e., when r = (n-1)/2 or r = (n+1)/2. In either case the maximum value is e = (n - 1)(n + 1)/4.

5. If a complete bipartite graph K_r,s is regular, then r = s.

6. K_3,3 is trivalent.

7. The adjacency matrix of K_r,s is an (r+s) x (r+s) matrix. It can be written in the form of an r x r block of zeros and an s x s block of zeros on the leading diagonal and ones everywhere else.

8. • The degree of a vertex s in V₁ is the number of classes that student s is taking.
   • The degree of a vertex c in V₂ is the number of students in class c.
   • If two vertices s₁ and s₂ in V₁ are adjacent to the same vertex c in V₂ then both students s₁ and s₂ are in class c .
   e-mail: C. Mawata © C. Mawata