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

### Subjects List

**Database (48)**

**Accounting (39)**

**Economics (34)**

**Finance (54)**

**Programming (122)**

**Management (69)**

**Marketing (25)**

**Report Writing (52)**

**Engineering (79)**

**Statistics (39)**

**Business Studies(45)**

**Case Studies (15)**

**Networking (26)**

**UML (9)**

**Science (23)**

**Nursing (11)**

**MATLAB (17)**

**Psychology (6)**

**Math (20)**

**Data Structure (9)**

**Python (15)**

**HRM (25)**

**IT (21)**

**Computer Science (57)**

**Law (4)**

**Essay (3)**

**Data Analysis (2)**

**Big Data (3)**

**Philosophy (2)**

**History (1)**