2.3.1. Walk, trail path in a graph
Let u and v be (not necessarily distinct) vertices of a graph G. A u-v walk W of G is a finite alternating sequence


Figure 2.7. A walk with length k = 6.
Two u-v walks and
are
equal iff
and ui = vi for
. Otherwise W1 and W2
are different.
A u-v walk is closed if u = v, otherwise () it
is open. A u-v trail is a u-v walk in which no edge is repeated, and a u-v path is a u-v walk
in which no vertex is repeated. A path with n
vertices is denoted by Pn.
Statement 2.8. Every path is a trail.
A non-trivial closed trail is
referred to as a circuit, and a
circuit whose vertices vi
are distinct called as cycle. A cycle
is even if its length is even; otherwise it is odd. A cycle of length n is an n-cycle and we denote it by Cn;
a 3-cycle is also called triangle. An
acyclic graph has no cycle.
In a connected graph G the distance d(u,v) between two vertices u and v is the minimum of the lengths of the u-v paths of G.
Theorem 2.9. A nontrivial graph is bipartite iff it contains no odd cycles.
Proof.
-
Suppose that G is bipartite. Let V1
and V2 be the two vertex classes. Let be a cycle. Let
.
Then
,
. Generally,
iff i is odd. Since vt must be in V2, so t
is even.
-
Suppose that G does not contain odd cycle. Let an arbitrary vertex. Let
and
.
There is no edge between two vertices in the same vertex-class. (otherwise there is an odd cycle in G.)
So, the graph is bipartite.