Mathematics for Computer Science

9.12. Summary of Relational Properties 263

letRndenote the length-nwalk relation in the digraphR, that is,

a RnbWWDthere is a length-nwalk fromatobinR:

Prove that
RnDCn (9.10)

for alln 2 N.

Problem 9.9.
IfRis a binary relation on a set,A, thenRkdenotes the relational composition of
Rwith itselfktimes.

(a)Prove that ifRis a relation on a finite set,A, then

a .R[IA/nb iff there is a path inRof length lengthnfromatob:

(b)Conclude that ifAis a finite set, then

RD.R[IA/jAj^1 : (9.11)

Problem 9.10.
In this problem we’ll consider some special closed walks in graphs calledEuler
tours, named after the famous mathematician Leonhard Euler. (Same Euler as for
the constante2:718—he did a lot of stuff.)

Definition. An Euler tour of a graph is a closed walk that includes every edge
exactly once.

So how do you tell in general whether a graph has an Euler tour? At first glance
this may seem like a daunting problem (the similar sounding problem of finding
a cycle that touches every vertex exactly once is one of those million dollar NP-
complete problems known as theTraveling Salesman Problem)—but it turns out to
be easy.

(a)Show that if a graph has an Euler tour, then the in-degree of each vertex equals
its out-degree.