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 Kn and the complement of Kn,m?
- Show that each bipartite graph on n vertices has at most bn2/4c edges. Is this bound best possible; that is, can we find an upper bound that is less than bn2/4c?
- We define a complete tripartite graph, Ka,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 Ka,b,c. (Both should be a function of a,b, and c.)
- Write a definition for the complete m-partitite graph Kx1,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.
- Find a formula for the maximum number of leaves for an m-ary tree of height h.
(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 .
