(Image: 5
Let G (V, E) be a digraph in which every vertex is a source, or a sink, or both a
sink and a source.
(a)
Prove that G has neither self-loops nor anti-parallel edges.
(b)
Let Gu
=
(V, Eu) be the undirected graph obtained by erasing the direction on
the edges of G. Prove that G" has chromatic number 1 or 2.
You are not required to draw anything in your proofs.)
