Introduction to Graph Theory · Problem 4.9

Digraphs and multidigraphs — Darij Grinberg

Mathematics — Graph Theory · strong-components-eclectic-cycles

Problem

Let

D = (V, E, \psi)

be a multidigraph. Let

A

B

and

C

be three subsets of

V

such that the induced subdigraphs

D[A]

D[B]

and

D[C]

are strongly connected. A cycle of

D

will be called eclectic if it contains at least one arc of

D[A]

, at least one arc of

D[B]

and at least one arc of

D[C]

(although these three arcs are not required to be distinct). Prove the following: (a) If the sets

B \cap C

C \cap A

and

A \cap B

are nonempty, but

A \cap B \cap C

is empty, then

D

has an eclectic cycle. (b) If the induced subdigraphs

D[B \cap C]

D[C \cap A]

and

D[A \cap B]

are strongly connected, but the induced subdigraph

D[A \cap B \cap C]

is not strongly connected, then

D

has an eclectic cycle. [Note: Keep in mind that the multidigraph with 0 vertices does not count as strongly connected.]