Mathematics for Computer Science

9.11. Summary of Relational Properties 349

Explain why there must be an edge not on the trail that starts or ends at a vertex on
the trail.

In the remaining parts, assume the graph is weakly connected, and the in-degree
of every vertex equals its out-degree. Letwbe thelongesttrail in the graph.

(c)Show that ifwis closed, then it must be an Euler tour.

Hint:part (b)

(d)Explain why all the edges starting at the end ofwmust be onw.

(e)Show that ifwwas not closed, then the in-degree of the end would be bigger
than its out-degree.

Hint:part (d)

(f)Conclude that if the in-degree of every vertex equals its out-degree in a finite,
weakly connected digraph, then the digraph has an Euler tour.

Problem 9.9.
LetRbe a binary relation on a setA. RegardingRas a digraph, letW.n/denote
the length-nwalk relation in the digraphR, that is,

a W.n/bWWDthere is a lengthnwalk fromatobinR:

(a)Prove that

W.n/ıW.m/DW.mCn/ (9.11)

for allm;n 2 N, whereıdenotes relational composition.

(b)LetRnbe the composition ofRwith itselfntimes forn 0. SoR^0 WWDIdA,
andRnC^1 WWDRıRn.

Conclude that
RnDW.n/ (9.12)

for alln 2 N.

(c)Conclude that

RCD

[jAj

iD 1

Ri

whereRCis the positive length walk relation determined byRon the setA.