let be a graph, a path from the a to another is a sequence of edges such that the first edge is between and , the second is between and , and in general, for all , , the 'th edge is between and . we can also write .
a path in a directed graph is the same as a graph of a undirected graph, with one additional constraint: all the edges should be directed in the same direction, from the first to the last vertex.
a subpath is simply a path within a path, i.e. a path whose edges are a subset of another path, only if the edges in the subset are adjacent.
let be a connected unweighted graph and let be a path in ,
- the length of is defined as the number of edges in the path, , we write
- the distance between the vertices and is defined as the length of the minimal path between and , we denote by the distance in graph G between and and get:
if there is no path between and then
a subpath of a minimal path is also a minimal path.
let be a graph, let be a minimal path between two arbitrary vertices . for all , we denote by the subpath from to , .
assume in contradiction that there exist two indicies , such that there exists a path from to and , consider the path from to , , we get , which contradicts with our assumption that is the shortest path between and .
let be an undirected connected graph, let be an arbitrary vertex in , assume that , then:
- if then has atleast a single neighbor, , such that ,
- for each , a neighbor of , .
proof for 1
given that is connected and , so . let be a minimal path from to , it follows from lem-path-1 that: .
proof for 2
the vertex is a neighbor of , therefore . we have which means .
the number of vertices in a simple path is at most , the number of edges in a simple path is at most .
in a simple path no vertex repeats itself.