Grinberg-Introduction-Graph-Theory · Problem 4.4

Digraphs and multidigraphs

Mathematics — Graph Theory · digraph-mantel-analogue

Problem

Let

D

be a simple digraph with

n

vertices and

a

arcs. Assume that

D

has no loops, and that we have

a > n^2/2

. Prove the following: (a) The digraph

D

has a cycle of length 3. (b) We define an enhanced 3-cycle to be a triple

(u, v, w)

of distinct vertices of

D

such that all four pairs

(u,v)

(v,w)

(w,u)

and

(u,w)

are arcs of

D

. Then, the digraph

D

has an enhanced 3-cycle.