# 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*and the complement of_{n }*K*?_{n,m} - Show that each bipartite graph on
*n*vertices has at most b*n*^{2}*/*4c edges. Is this bound best possible; that is, can we find an upper bound that is less than b*n*^{2}*/*4c? - We define a complete tripartite graph,
*K*as the graph where the vertices can be partitioned into three sets,_{a,b,c }*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*. (Both should be a function of_{a,b,c}*a,b*, and*c*.) - Write a definition for the complete
*m*-partitite graph*K*_{x}_{1,x}_{2,...,x}._{m} - 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.- Find a formula for the maximum number of leaves for an
*m*-ary tree of height*h*.

- Find a formula for the maximum number of leaves for an

(For any *m,h *∈N.)

- 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*.