LearnMathOnline

Definition (Walk). A walk of length \(n\) from vertex \(v_0\) to \(v_n\) in a graph \(G\) is a sequence of vertices and edges of the form \[v_0,e_1,v_1,e_2,v_2,\ldots,v_{n-1},e_n,v_n\] where edge \(e_i\) is an edge between vertices \(v_{i-1}\) and \(v_i\) for all \(i=1,2,\ldots,n\). A circuit or a closed walk is a walk whose endpoints are the same (i.e., \(v_0=v_n\)).

Remark. A walk may repeat a vertex and an edge. A path of length \(n\) between vertices \(v_0\) to \(v_n\) is a walk of length \(n\) from \(v_0\) to \(v_n\) that has no repeated vertices and edges which can be simply written in the form \(v_0v_1v_2\cdots v_n\) in a simple graph.

Example. In the above graph \(G\), \(abcf\) is a walk and also a path of length \(3\). \(abcfb\) is a simple walk of length 4, but not a path because of the repeated vertex \(b\). The walk \(abcfba\) is a circuit of length 6.

Definition (Distance). The distance between vertices \(u\) to \(v\) in a graph \(G\), denoted by \(\operatorname{d}(u,v)\), is the minimum length of a path (or a walk) between \(u\) and \(v\). If there is no path between \(u\) and \(v\), we define \(\operatorname{d}(u,v)=\infty\).

Example. In the above graph \(G\), \(\operatorname{d}(a,a)=0\), \(\operatorname{d}(a,e)=1\), and \(\operatorname{d}(a,f)=2\).

Remark. The concept of distance is used to define Erdös number (the collaboration distance from Paul Erdös), Bacon number etc. In 2016, the average distance in the Facebook friend graph was \(4.57\), i.e., \(3.57\) intermediaries or "degrees of separation." It is said that everyone on the planet is connected to everyone else by six other people ("six degrees of separation").

Definition (Connected graph). A graph \(G\) is connected if there is a path between any two vertices of \(G\). \(K_1\) is defined to be connected. A graph is disconnected if it is not connected. A connected component or simply component of a graph \(G\) is a connected subgraph of \(G\) that is not a proper subgraph of another connected subgraph of \(G\).

Example. The above graph \(G\) is connected, i.e., it has one connected component. But the above disconnected graph \(H\) has two connected components.

Example. \(99.91\%\) of Facebook users belong to a single large connected component in the Facebook friend graph.

Definition (Cut vertex). A vertex \(v\) is a cut vertex of a graph \(G\) if \(G-v\) has more connected components than \(G\). An edge \(e\) is a cut edge or bridge of a graph \(G\) if \(G-e\) has more connected components than \(G\).

Example. The vertex \(e\) is a cut vertex of the above graph \(G\). Note that if \(v\) is a cut vertex of a connected graph \(G\), then \(G-v\) is disconnected. The edge \(\{f,g\}\) is a bridge of both \(G\) and \(H\). Note that \(K_n,\;n\geq 3\) has no cut vertices and bridges.

Definition (Edge connectivity). For a connected graph \(G=(V,E)\), an edge cut of \(G\) is a subset \(E'\) of \(E\) for which \(G-E'\) is disconnected. The edge connectivity of \(G\), denoted by \(\lambda(G)\), is the minimum number of edges in an edge cut of \(G\). We define \(\lambda(G)=0\) for disconnected graphs \(G\) and for \(G=K_1\).

Remark. Note that \(\lambda(G)=n-1\) if and only if \(G=K_n\). So \(0\leq \lambda(G)\leq n-1\) for any graph \(G\) on \(n\) vertices.

Example. \(\lambda(P_n)=1\) for \(n\geq 2\) and \(\lambda(C_n)=2\).

Definition (Vertex connectivity). For a connected graph \(G=(V,E)\), a vertex cut or separating set of \(G\) is a subset \(V'\) of \(V\) for which \(G-V'\) is disconnected. The vertex connectivity of \(G\), denoted by \(\kappa(G)\), is the minimum number of vertices in a vertex cut of \(G\). Since \(K_n\) has no vertex cut, we define \(\kappa(K_n)=n-1\). We define \(\kappa(G)=0\) for disconnected graphs \(G\). A graph \(G\) is \(k\)-connected if \(\kappa(G)\geq k\).

Remark. \(0\leq \kappa(G)\leq n-1\) for any graph \(G\) on \(n\) vertices. Note that if \(G\) is \(k\)-connected, then \(G\) is \(j\)-connected for all \(j=0,1,\ldots,k\). Also \(\kappa(G)\) is the greatest integer \(k\) for which \(G\) is \(k\)-connected.

Example.

Theorem (Whitney, 1932). For a simple graph \(G\), \(\kappa(G)\leq\lambda(G)\leq \delta(G)\).

Solution. (a) The vertex cuts of \(G\) of size at most \(2\) are \(\{b\},\{b,a\},\{b,c\},\{b,d\},\{b,e\}\). The edge cuts of \(G\) of size at most \(2\) are \(\{\{b,c\},\{b,d\}\}, \{\{b,a\},\{b,e\}\}\), and the sets of two edges incident with \(a,e,c,d\).

(b) \(\kappa(G)=1\), \(\lambda(G)=2\), \(\delta(G)=2\), and we have \[\kappa(G)=1 < 2=\lambda(G)=\delta(G).\]

Definition (Walk). A walk of length \(n\) from vertex \(v_0\) to \(v_n\) in a digraph \(G\) is a sequence of vertices and arcs of the form \[v_0,e_1,v_1,e_2,v_2,\ldots,v_{n-1},e_n,v_n\] where arc \(e_i\) is an arc from \(v_{i-1}\) to \(v_i\) for all \(i=1,2,\ldots,n\). A circuit or a closed walk is a walk whose endpoints are the same (i.e., \(v_0=v_n\)).

Remark. A walk may repeat a vertex and an arc. A directed path of length \(n\) from \(v_0\) to \(v_n\) is a walk of length \(n\) from \(v_0\) to \(v_n\) that has no repeated vertices and arcs which can be simply written in the form \(v_0v_1v_2\cdots v_n\) in a simple digraph.

Definition (Strongly connected digraph). A digraph \(G\) is strongly connected if there is a walk from \(u\) to \(v\) and a walk from \(v\) to \(u\) for any two vertices \(u\) and \(v\). A directed graph \(G\) is weakly connected if there is a walk between any two vertices in the underlying undirected graph of \(G\).

Remark. If a digraph \(G\) is strongly connected, then it is weakly connected. The converse is not true in general.

Example. Above digraph \(G\) is strongly connected and weakly connected. Above digraph \(H\) is not strongly connected (since there is no walk from \(a\) to \(b\)) but \(H\) is weakly connected.

Definition (Strongly connected component). A subgraph of a digraph \(G\) is called a strongly connected component if it is strongly connected and is not contained in a larger strongly connected subdigraph of \(G\).

Example. The above digraph \(H\) has 3 strongly connected components: \(a;e\); and the subdigraph on vertices \(b,c,d\) with arcs \((b,c),(c,d),(d,b)\).

Example. A webgraph in 1999 with 200 millions vertices and 1.5 billion arcs was studied. It was not strongly connected but it had lots of strongly connected components covering \(90\%\) of the vertices of the webgraph.

Connectivity