2 Some basic notions 2.2 Some basic notions 2.4 ***Graphs and matrices : A little peek***

2.3 Walks, Trails and Paths

Definition 2.29.

(Walk, Trail , Path and Cycle) An ordered set of vertices $P=v_{0}\ldots v_{k}$ is said to be a walk from $v_{0}$ to $v_{k}$ if $v_{i}\sim v_{i+1}$ . A walk $P=v_{0}\ldots v_{k}$ is said to be a trail from $v_{0}$ to $v_{k}$ if $(v_{i},v_{i+1})$ are distinct for all $i$ i.e., no repeated edges. A trail $P=v_{0}\ldots v_{k}$ is said to be a path from $v_{0}$ to $v_{k}$ if $v_{i}$ ’s are distinct i.e., no repeated vertices. A walk is closed if $v_{k}=v_{0}$ . A walk or trail is said to be closed if $v_{k}=v_{0}$ and else open. A closed trail is also called as a circuit. A circuit $C=v_{0}\ldots v_{k-1}v_{0}$ with no repetition of intermediate vertices is called a cycle i.e., $v_{0},\ldots,v_{k-1}$ are distinct. In other words, $v_{0}\ldots v_{k-1}$ is a path and $v_{k-1}\sim v_{0}$ .

Path as defined above is also referred to as simple path or self-avoiding walk.

Exercise 2.30.

For $v\neq w$ , show that there exists a walk from $v$ to $w$ iff there exists a trail from $v$ to $w$ iff there exists a path from $v$ to $w$ .

The question can be re-framed as: For $v\neq w$ , show that the following are equivalent:

1.

there exists a walk from $v$ to $w$
2.

there exists a trail from $v$ to $w$
3.

path from $v$ to $w$ .

By definition, a path is a trail and a trail is a walk. Hence $(3)\implies(2)\implies(1)$ is clear. To prove $(1)\implies(3)$ we see the following claim:
Claim : For every walk from a vertex $u$ to another distinct vertex $v$ , we can find a path from $u$ to $v$ .
Proof: We use induction on the length of the walk.
Base case: $|\mathcal{W}|=1$ . It is trivially true that such a walk is a path.
Inductive hypothesis: Assume it is true that for every walk from $u$ to $v$ of length less than $w$ we can find a path from $u$ to $v$ .
Inductive case: Suppose $|\mathcal{W}|=w$ . If all the vertices in $\mathcal{W}$ are distinct, we are done. If not, there is a repeated vertex, say $x$ . Now we can decompose $\mathcal{W}=\mathcal{W}_{1}\cup\mathcal{W}_{2}\cup\mathcal{W}_{3}$ where $\mathcal{W}_{1}$ is the segment of $\mathcal{W}$ from $v_{0}$ to the first appearance of $x$ , $\mathcal{W}_{2}$ is the segment of $\mathcal{W}$ from the first appearance of $x$ to the last appearance of $x$ , and $\mathcal{W}_{3}$ is the segment of $\mathcal{W}$ from the last appearance of $x$ to $v_{k}$ . Thus $\mathcal{W}^{\prime}:=\mathcal{W}_{1}\cup\mathcal{W}_{3}$ is a walk from $u$ to $v$ of length strictly smaller than that of $\mathcal{W}$ and by our hypothesis, there is a path from $u$ to $v$ .

$\square$

For $v\neq w$ , we say that $v$ is connected to $w$ (denoted by $v\rightarrow w$ ) if there exists a path from $v$ to $w$ . We shall always assume that $v\rightarrow v$ . Show that $\rightarrow$ induces an equivalence relation. Define the component of $v$ as $C_{v}:=\{w:v\to w\}$ . If $v\to w$ , then $C_{v}=C_{w}.$ We shall also abuse notation and denote the induced graph on $C_{v}$ by $C_{v}$ as well.

A graph is said to be connected if there exists a path from $v$ to $w$ for all $v\neq w$ i.e., $v\rightarrow w$ for all $v\neq w$ . A subgraph is said to be connected if it is connected as a graph.

Exercise(A) 2.31.

Show that $\to$ partitions $V$ into equivalence classes and the equivalence class of $v$ is $C_{v}$ . Show that $C_{v}$ is the maximal connected subgraph containing $v$ .

The equivalence classes induced by $\to$ are called as (connected) components and the number of (connected) components are denoted by $\beta_{0}(G)$ .

Lemma 2.32.

If $G$ has $n$ vertices and $m$ edges then $\beta_{0}(G)\geq n-m$ .

Proof.

We prove using induction on $m$ . Start with a graph on $n$ vertices and no edges. It has $n$ components. Add edges one by one. Addition of an edge decreases $\beta_{0}(G)$ by at most $1$ and hence proved. ∎

Exercise 2.33.

Show that $\beta_{0}(G)=1$ iff for all $v\neq w\in G$ , $v\to w$ .

We call the graph to be connected if $\beta_{0}(G)=1$ .

Exercise(A) 2.34.

Show that $\delta(G),\Delta(G),d(G),\beta_{0}(G)$ are all graph invariants.

Lemma 2.35.

Let $G$ be a simple graph with at least two vertices. Show that $G$ must contain at least two vertices with the same degree.

Proof.

This is just a straightforward application of Pigeon-hole Principle. Define $B_{i}=\{v\in V\colon d_{v}=i\}$ for $i=0,1,\dots,n-1$ . Then, since $\sum_{i}|B_{i}|=n$ , either there is a $i$ such that $|B_{i}|\geq 2$ and we are done, or $|B_{i}|=1$ for all $i$ . But then since $|B_{n-1}|=1$ , we have a $v\in V$ such that $v\sim w$ for any $w\in V$ . This contradicts the existence of a degree-zero vertex (from $B_{0}$ ), thus there is a $i$ from $0$ to $n-1$ such that $|B_{i}|>1$ . ∎