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