Introduction to Graph Theory · Problem 4.4

Digraphs and multidigraphs — Darij Grinberg

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.