Since a graph cannot contain a path longer than n -1, where n is the number of vertices, and given that Υ is connected, then Q n-1 contains all paths and therefore all edges of Υ. Thus we have Q |Υ|-1 = Υ. Moreover, every path from v to x of length j is an extension of a path of length j -1 from v to some x ′ by the edge x ′ x. Thus Q j contains all vertices and edges of