Computer science - math 1135 - Graph theory and applications

(a) Let H be the graph below: (i) draw a regular simple graph Fu of degree 4, such that H can be realised as an induced sub- graph of FH. (6 marks) (ii) Does there exist a regular simple graph K with fewer vertices than the graph Fu in part (i) such that H is an induced subgraph of K? Either show that there exists one by drawing it, or prove that FH is the smallest such graph. (4 marks) (b) Let n be a non-negative integer. Let G be a non-regular connected graph with n vertices and suppose that dmar and dmin are the largest and smallest entries of the degree sequence of G. Suppose that FG is the regular graph that contains G as an induced subgraph obtained using the copy construct tion. Write down a formula for the number of vertices of Fc in terms of n, dmax and dmin fully justifying your reasoning.