path

let $\text{[math]}$ be a graph, a path from the a $\text{[math]}$ to another $\text{[math]}$ is a sequence of edges
$\text{[math]}$ such that the first edge is between $\text{[math]}$ and $\text{[math]}$ , the second is between $\text{[math]}$ and $\text{[math]}$ , and in general, for all $\text{[math]}$ , $\text{[math]}$ , the $\text{[math]}$ 'th edge is between $\text{[math]}$ and $\text{[math]}$ . we can also write $\text{[math]}$ .
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.

the number of edges of a path $\text{[math]}$ is its length, denoted by $\text{[math]}$ .
[cite:;taken from @graph_diestel_2017 chapter 1.3 paths and cycles]

let $\text{[math]}$ be a connected unweighted graph and let $\text{[math]}$ be a path in $\text{[math]}$ ,

the length of $\text{[math]}$ is defined as the number of edges in the path, $\text{[math]}$ , we write $\text{[math]}$
the distance between the vertices $\text{[math]}$ and $\text{[math]}$ is defined as the length of the minimal path between $\text{[math]}$ and $\text{[math]}$ , we denote by $\text{[math]}$ the distance in graph G between $\text{[math]}$ and $\text{[math]}$ and get:

$\text{[math]}$ if there is no path between $\text{[math]}$ and $\text{[math]}$ then $\text{[math]}$

a subpath of a minimal path is also a minimal path.

let $\text{[math]}$ be a graph, let $\text{[math]}$ be a minimal path between two arbitrary vertices $\text{[math]}$ . for all $\text{[math]}$ , we denote by $\text{[math]}$ the subpath from $\text{[math]}$ to $\text{[math]}$ , $\text{[math]}$ .
assume in contradiction that there exist two indicies $\text{[math]}$ , such that there exists a path $\text{[math]}$ from $\text{[math]}$ to $\text{[math]}$ and $\text{[math]}$ , consider the path $\text{[math]}$ from $\text{[math]}$ to $\text{[math]}$ , $\text{[math]}$ , we get $\text{[math]}$ , which contradicts with our assumption that $\text{[math]}$ is the shortest path between $\text{[math]}$ and $\text{[math]}$ .

let $\text{[math]}$ be an undirected connected graph, let $\text{[math]}$ be an arbitrary vertex in $\text{[math]}$ , assume that $\text{[math]}$ , then:

if $\text{[math]}$ then $\text{[math]}$ has atleast a single neighbor, $\text{[math]}$ , such that $\text{[math]}$ ,
for each $\text{[math]}$ , a neighbor of $\text{[math]}$ , $\text{[math]}$ .

proof for 1
given that $\text{[math]}$ is connected and $\text{[math]}$ , so $\text{[math]}$ . let $\text{[math]}$ be a minimal path from $\text{[math]}$ to $\text{[math]}$ , it follows from path.html that: $\text{[math]}$ .

proof for 2
the vertex $\text{[math]}$ is a neighbor of $\text{[math]}$ , therefore $\text{[math]}$ . we have
$\text{[math]}$ which means $\text{[math]}$ .

the number of vertices in a simple path is at most $\text{[math]}$ , the number of edges in a simple path is at most $\text{[math]}$ .

in a simple path no vertex repeats itself.