Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MTH6105 – Algorithmic Graph Theory

Assessed Coursework 1

Spring 2023

1. Let the degree sequence of a graph G be the sequence of length |V (G)| that contains the degrees of the vertices of G in non-increasing order.

(a) For each of the following sequences, either draw a simple graph whose de-

gree sequence is equal to that sequence, or explain why such a graph does not exist:  (i) (4, 4, 4, 2, 2), (ii) (4, 2, 2, 1, 1), (iii) (3, 3, 3, 2, 1), (iv) (4, 3, 3, 2, 1), (v) (2, 2, 2, 1, 1).

(b) Consider a simple graph with 9 vertices, such that the degree of each vertex is

either 5 or 6. Prove that there are at least 5 vertices of degree 6 or at least 6 vertices of degree 5.

2. Let G be a graph and e ∈ E(G).  Let H be the graph with V (H) = V (G) and E(H) = E(G)/{e}. Then e is a bridge of G if H has a greater number of connected components than G.

(a) Let  G  be  the  simple  graph  with  V (G)  =  {u,v,w,x,y,z}  and  E(G)  =

{uy,vx,vz,wx,xz}.  For each e  ∈ E(G), state whether e is a bridge of G. Justify your answer.

(b) Assume that G is connected and that e is a bridge of G with endpoints u and v .

Show that H has exactly two connected components H1 and H2 with u ∈ V (H1 ) and v ∈ V (H2 ).  To this end, you may want to consider an arbitrary vertex w ∈ V (G) and use a u−w-path in G to construct a u−w-path or a v−w-path in H .

(c) Show that e is a bridge of G if and only if it is not contained in a cycle of G.

3.   (a) Determine the Pr¨ufer code of the following tree.

(b) Draw  the  trees  with  Pr¨ufer  codes  (i)  (3, 2, 3, 2, 3),  (ii)  (5, 5, 5, 5, 5),  and

(iii) (6, 5, 4, 3, 2).