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

of vertices and edges, beginning with vertex u and ending with vertex v, such that for . The number k is called the length of W.

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.

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.