Introduction to Graph Theory · Problem 4.14

Digraphs and multidigraphs — Darij Grinberg

Mathematics — Graph Theory · tournaments-3-cycle-reversal

Problem

If a tournament

D

has a 3-cycle

(u, v, w)

, 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 three arcs

(u, v)

(v, w)

and

(w, u)

are replaced by the three new arcs

(v, u)

(w, v)

and

(u, w)

. (Visually speaking,

D'_{u,v,w}

is obtained from

D

by turning the arrows on the arcs

(u, v)

(v, w)

and

(w, u)

around.) We say that the new tournament

D'_{u,v,w}

is obtained from the old tournament

D

by a 3-cycle reversal operation. Now, let

V

be a finite set, and let

E

and

F

be two tournaments with vertex set

V

. Prove that

F

can be obtained from

E

by a sequence of 3-cycle reversal operations if and only if each

v \in V

satisfies

\deg^-_E(v) = \deg^-_F(v)

. (Note that a sequence may be empty, which allows handling the case

E = F

even if

E

has no 3-cycles to reverse.)