Graph Theory Lessons

1. S₃, S₅, S₈, all have chromatic number 2. In fact all stars have chromatic number 2 (color the vertex of degree n - 1 one color and all the degree 1 vertices another color) .

2. Since stars have chromatic number 2, they are bipartite.

3. K_{1, n - 1} isomorphic to S_n.

4. K_r,s,t has r vertices of degree s + t, and s vertices of degree t + r, and t vertices of degree r + s. The sum of the degrees of the vertices is therefore r ( s + t ) + s ( t + r ) + t ( r + s ) = 2rs + 2st + 2rt. The number of edges is rs + st + rt.

5. If a complete tripartite graph K_r,s,t is regular, then all the vertices have the same degree so
   r + s = s + t = r + t.
   However, r + s = s + t implies r = t, and s + t = r + t implies s = r, so we have that r = s = t.

6. If a complete tripartite graph is regular of degree m then from problem 5, r = s = t and also r + s = s + t = r + t = m, so r = s = t = m/2. The graph is K_{m/2, m/2, m/2}. Note that this tells us that m has to be even.

7. For a complete tripartite graph to be trivalent is must be regular of degree 3. But then by problem 6, we need r = s = t = 3/2 which is impossible, since r, s, and t are integers.

8. The adjacency matrix of K_2,3,4 is
   

9. A complete tripartite graph has chromatic number 3.