Abstract:
A congruence relation of a path is an equivalence relation on the set of its vertices all of whose classes are independent subsets. It is proved (theorem 1) that the number of all congruence relations of a path with $m$ edges equals to the number of all equivalence relations on a $m$-element set. For a given connected graph $G$ theorem 2 determines the length of the shortest path whose quotient-graph is $G$.