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.