Section 5.2 Connectivity of Graphs

SECTION 5.2 Connectivity of Graphs

Definitions

For the following definitions, let u and v be vertices of a graph G:

Walk	A *walk* from u to v is a finite sequence of adjacent vertices and edges of G and is in the form v₀e₁v₁e₂ . . . v_n_-1e_nv_n where each *v_i* represents a vertex and each *e_i* represents an edge, v₀ = u (the starting point) and *v_n* = v, for all i = 1, 2, . . . n.
Path	A *path* from u to v is a walk from u to v that does not contain a repeated edge. A path from u to v is in the form of a walk u = v₀e₁v₁e₂ . . . v_n_-1e_nv_n= v, where all the *e_i* are distinct ( that is, *e_i e_k* for any ik).
Simple Path	A path from u to v that does not contain a repeated vertex. A simple path is in the form of a walk u = v₀e₁v₁e₂ . . . v_n_-1e_nv_n= v, where all the *e_i* are distinct and all the *v_jare also distinct (that is, v_j v_p* for any *j p*).
Closed Walk	A walk that starts and ends at the same vertex. A closed walk is in the form v₀e₁v₁e₂ . . . v_n_-1e_nv_n, where v₀ = *v_n*.
Circuit	A closed walk which does not contain a repeated edge. A circuit is in the form of a walk v₀e₁v₁e₂ . . . v_n_-1e_nv_n, where v₀ = *v_n* and all the *e_i* are distinct.
Simple Circuit	A circuit that does not have any other repeated vertex except the first and last.
Connected	A graph G is *connected*, if, and only if, given any two vertices u and v in G, there is a walk from u to v. It can be written as : G is connected vertices u, v V(G), a walk from u to v.
Connected Component	A graph H is a *connected component* of a graph G, if, and only if, 1. H is a subgraph of G; 2. H is connected; 3. no connected subgraph of G has H as a subgraph and contains vertices or edges that are not in H.

Example:

Given the graph below,

(a) determine which of the following walks are paths, simple paths, circuits, or simple circuits:

(i) v₂e₃v₃e₅v₄e₇v₆ (ii) e₂e₃e₉e₇e₇e₅e₆

(iii) v₃v₄v₂v₃ (iv) v₅v₃v₄v₂v₃v₅

(b) find a walk of length 4, and a walk of length 8.

Euler Tours

Let G be a graph, and u and v be two vertices of G:

Euler circuit	An *Euler circuit* for G is a circuit that contains every vertex and every edge of G. It is a sequence of adjacent vertices and edges in G that starts and ends at the same vertex, uses every vertex of G at least once, and uses every edge of G exactly once.
Euler path	An *Euler path* from u to v is a sequence of adjacent edges and vertices that starts at u, ends at v, passes through every vertex of G at least once, and traverses every edge of G exactly once.

Other properties:

1.	If a graph has an Euler circuit, every vertex of that graph has even degree. (In contrast, a graph does not have an Euler circuit if some vertex of that graph has odd degree.)
2.	An Euler path exists from u to v if, and only if, G is connected, u and v have odd degree, and all other vertices of G have even degree.

Example: Do either of the following graphs have an Euler circuit or an Euler path?

Graph 1

Graph 2

Hamiltonian Circuits

Given graph G, a Hamiltonian path is a path that contains every vertex of G. A Hamiltonian circuit is a simple circuit that includes every vertex of G.

Other properties:

If graph G has a Hamiltonian circuit, then G has a subgraph H with the following properties:
1.	H contains every vertex of G;
2.	H is connected;
3.	H has the same number of edges as vertices; and
4.	every vertex of H has degree 2.

Example:

Show that the diagram below contains a Hamiltonian circuit.

Go to next section review

Go to Class Agenda