4 Exercise 4

  • June 27, 2021

4 Exercise 4 Consider a weakly connected, directed graph D= (V, A) with |V. Recall that id(u)denotes the in- degree of and that od(u)denotes the out-degree- of. Assume that id(v)=od(v)for all∈v Let→x1→→xk= be longest directed circuit in 2.0p a Consider the directed graph D’=(V, A’)that contains all vertices of D, and all arrows of D that are not in the longest directed circuit. Prove that it also holds in D’ that id() od()for all vEV 3.0p b Let ; with s is k, be an arbitrary vertex on the longest directed circuit and let(,) E A be an arbitrary arrow out of;. Prove that(, is included in the longest directed circuit.