MTH607 graph theory assignment 2

For full marks, your answers should be clear, precise and carefully argued. Just having “the right idea” will only give you a passing mark.

• What can you say about the complement of K_n and the complement of K_n,m?
• Show that each bipartite graph on n vertices has at most bn²/4c edges. Is this bound best possible; that is, can we find an upper bound that is less than bn²/4c?
• We define a complete tripartite graph, K_a,b,c as the graph where the vertices can be partitioned into three sets, A, B, C, and there is an edge from every vertex in partition A to every vertex in both partitions B and C, similarly for B, and C, and no edges within a partition. Find the number of vertices and edges in the general complete tripartite graph K_a,b,c. (Both should be a function of a,b, and c.)
• Write a definition for the complete m-partitite graph K_x1,x2,...,xm.
• An m-ary tree is defined as a rooted tree where each parent has at most m That is, for any internal vertex other than the root the degree is at most m + 1. The degree of the root is at most m. The height of a tree is defined to be the maximum number of vertices between the root and any leaf. For example, an isolated vertex has height 0, and a star (rooted at the center) has height 1.
  1. Find a formula for the maximum number of leaves for an m-ary tree of height h.

(For any m,h ∈N.)

3. Draw a full binary tree (that is every non-leaf has exactly two children) of height 3.

• Show that G = (V,E) is connected if and only if for each nontrivial partition of V (that is, each partition V = X ∪ Y with X,Y 6= ∅) there exists an edge with one endpoint in X and the other in Y .