MathDB

A directed graph (any two distinct vertices joined by at most one directed line) has the following property: If

x, u,

and

v

are three distinct vertices such that

x \to u

and

x \to v

, then

u \to w

and

v \to w

for some vertex

w

. Suppose that

x \to u \to y \to\cdots \to z

is a path of length

n

, that cannot be extended to the right (no arrow goes away from

z

). Prove that every path beginning at

x

arrives after

n

steps at

z.

56