2 Connectivity of general graph
A walk is a sequence of adjacent vertices. For vertices \(u, v \in V\), the walk between them is a sequence starting at \(u\) and ending at \(v\).
Two vertices \(u\) and \(v\) are said to be reachable if there is a walk between them.
A graph is preconnected if every pair of vertices is reachable from one another.
A graph is connected if it is preconnected and contains at least one vertex.
For a subset of vertices \(S \subseteq V\), the edge boundary \(\partial S\) consists of all edges with exactly one endpoint in \(S\) and the other in \(S^c\).
If there is a walk going from a vertex \(u \in S\) to a vertex \(v \in S^c\), then there is at least one edge that goes from \(S\) to \(S^c\).
In a connected graph, every set of vertices \(S\) different from the empty set and the universal set (\(S \neq \emptyset \) and \(S \neq V\)) has a non-empty edge boundary, that is \(\partial S \neq \emptyset \).