MathDB

Let

G

be a complete directed graph with

100

vertices such that for any two vertices

x,y

one can find a directed path from

x

y

.
a) Show that for any such

G

, one can find a

m

such that for any two vertices

x,y

one can find a directed path of length

m

from

x

y

(Vertices can be repeated in the path)
b) For any graph

G

with the properties above, define

m(G)

to be smallest possible

m

as defined in part a). Find the minimim value of

m(G)

over all such possible

G

's.

6