Introduction to Graph Theory · Problem 4.15

Digraphs and multidigraphs — Darij Grinberg

Mathematics — Graph Theory · tournaments-transitive-2-path-reversal

Problem

A tournament

D = (V, A)

is called transitive if it has no 3-cycles. If a tournament

D = (V, A)

has three distinct vertices

u

v

and

w

satisfying

(u, v) \in A

and

(v, w) \in A

, then we can define a new tournament

D''_{u,v,w}

as follows: The vertices of

D''_{u,v,w}

shall be the same as those of

D

. The arcs of

D''_{u,v,w}

shall be the same as those of

D

, except that the two arcs

(u, v)

and

(v, w)

are replaced by the two new arcs

(v, u)

and

(w, v)

. We say that the new tournament

D''_{u,v,w}

is obtained from the old tournament

D

by a 2-path reversal operation. Let

D

be any tournament. Prove that there is a sequence of 2-path reversal operations that transforms

D

into a transitive tournament.