(b) Write a pseudocode algorithm based on BFS that constructs a proper 2-vertex colouring of a connected simple graph, or else determines that the graph is not 2-vertex-colourable. Algorithm 4.31 Breadth-First Search procedure BF S(G: connected simple graph with vertices V1, V2, ..., Un) T:= tree consisting only of vertex vi Q := [v1] {Q is the queue of unprocessed vertices} while Q is not empty do begin V := first vertex in Q remove v from Q {now process vertex v} while v has a neighbour not in T do begin w := first neighbour of v not in T append w to the end of Q T:=T + vw end end {T is the breadth-first spanning tree of G}