Connectivity

Graphs

• A walk in graph `G` is a finite sequence of edges of the form `v_0 v_1, v_1 v_2, cdots, v_(m-1), v_m`, also denoted by `v_0 to v_1 to v_2 to cdots to v_m`, in which any two consecutive edges are adjacent or identical. The number of edges in a walk is called its length.
• A trail is a walk in which all edges are distinct.
• A path is a walk in which all vertices are distinct (except, possibly, `v_0 = v_m`).
• A walk, path or trail is closed if `v_0 = v_m`, a closed path with at least one edge is a cycle.

A graph is connected if and only if there is a path between each pair of vertices.

A graph `G` is bipartite if and only if every cycle of `G` (if exist) has even length. In other words, A bipartite graph has no odd length cycle.

Let `G` be a simple graph on `n` vertices. If `G` has `k` components, then the number `m` of edges of `G` satisfies `n-k le m le (n-k)(n-k+1)//2`.

Let `k = 2`, it follows:

Any simple graph with `n` vertices and more than `(n-1)(n-2)//2` edges is connected.

Menger theorems

In a graph `G`,
• A disconnecting set is a set of edges whose removal increases the number of components of `G`.
• A cutset is a minimal disconnecting set.
• A bridge is a cutset which has only one edge.
If `G` is a connected graph, its edge-connectivity `lambda(G)` is the size of the smallest cutset in `G`. We say that `G` is `k`-edge-connected if `lambda(G) ge k`.

• A separating set in a graph `G` is a set of vertices whose deletion increases the number of components of `G`.
• A cut-vertex is a separating set which contains only one vertex.
If `G` is connected and not a complete graph, its (vertex) connectivity `kappa(G)` is the size of the smallest separating set in `G`. We also say that `G` is `k`-connected if `kappa(G) ge k`.

(Menger, 1927)
• A graph `G` is `k`-edge-connected if and only if any two distinct vertices of `G` are joined by at least `k` paths, no two of which have any edges in common.
• A graph `G` with at least `k+1` vertices is `k`-connected if and only if any two vertices of `G` are joined by at least `k` paths, no two of which have any other vertices in common.

If `G` is a connected graph, then `kappa(G) le lambda(G) le delta(G)`, where `delta(G)` is the smallest vertex-degree in `G`.

There are striking and unexpected similarities between the properties of cycles and cutsets. The reasons will become clear in Chapter 7.

Digraphs

Definitions of walks, trails, paths and cycles in digraphs are similar; note that although a trail cannot contain a given arc `vw` more than once, it can contain both `vw` and `wv`. for example, `z to w to v to w to u`.

• A digraph `D` is connected if it cannot be expressed as the union of two digraphs; this is equivalent to saying that the underlying graph of `D` is a connected graph.
• `D` is strongly connected if, for any two vertices `v` and `w` of `D`, there is a directed path from `v` to `w`.
Every strongly connected digraph is connected.

Define a graph `G` to be orientable if each edge of `G` can be directed so that the resulting degraph (an orientation) is strongly connected.

(H. E. Robbins) A connected graph `G` is orientable if and only if each edge of `G` lies in at least one cycle; that is to say, `G` has no bridge.

Eulerian graphs and digraphs

Eulerian graphs

A connected graph `G` is Eulerian if there exists a closed trail (Eulerian trail) that includes every edge of `G`. A non-Eulerian graph `G` is semi-Eulerian if there exists a (non-closed) trail that includes every edge of `G`.

Any Eulerian graph is orientable, since we simply follow any Eulerian trail, directing the edges in the direction of the trail as we go.

If `G` is a graph in which the degree of each vertex is at least 2, then `G` contains a cycle.

(Euler, 1735) A connected graph `G` is Eulerian if and only if the degree of each vertex of `G` is even.

A connected graph is Eulerian if and only if its set of edges can be split up into edge-disjoint cycles (无公共边的圈).

A connected graph is semi-Eulerian if and only if it has exactly two vertices of odd degree.

In a semi-Eulerian graph, any semi-Eulerian trail must have one vertex of odd degree as its initial vertex and the other as its final vertex. Note also that, by the handshaking lemma, a graph cannot have exactly one vertex of odd degree.

(Fleury) Let `G` be an Eulerian graph. Then the following construction is always possible, and produces an Eulerian trail of `G`.
Start at any vertex `u` and traverse the edges in an arbitrary manner, subject only to the following rules:
1. erase the edges as they are traversed, and if any isolated vertices result, erase them too;
2. at each stage, use a bridge only if there is no alternative.

Eulerian digraphs

A strongly connected digraph `D` is Eulerian if there exists a closed directed trail (Eulerian trail) that includes every arc of `D`.

A strongly connected digraph `D` is Eulerian if and only if, for each vertex `v` of `D`, `"outdeg"(v) = "indeg"(v)`.

Hamiltonian graphs and digraphs

A connected graph `G` is Hamiltonian if there exists a cycle (Hamiltonian cycle) passing exactly once through each vertex of `G`. A non-Hamiltonian graph is semi-Hamiltonian if there exists a path through every vertex.

(Ore, 1960) If `G` is a simple graph with `n` (`ge 3`) vertices, and if `"deg"(v) + "deg"(w) ge n` for each pair of non-adjacent vertices `v` and `w`, then `G` is Hamiltonian.

(Dirac, 1952) If `G` is a simple graph with `n` (`ge 3`) vertices, and if `"deg"(v) ge n//2` for each vertex `v`, then `G` is Hamiltonian.

Hamiltonian digraphs

Let `D` be a strongly connected digraph with `n` vertices. If `"outdeg"(v) ge n//2` and `"indeg"(v) ge n//2` for each vertex `v`, then `D` is Hamiltonian.

If `T` is a tournament:
• `T` is strongly connected `iff` `T` is Hamiltonian.
• `T` is not strongly connected `iff` `T` is semi-Hamiltonian.