A graph is complete if every pair of vertices is adjacent. It is bipartite if the vertices can be partitioned into two sets X and Y such that all the edges join a vertex in X to a vertex in Y. A graph is complete bipartite if it contains all possible edges from a vertex in X to a vertex in Y. 

The complete graph on n vertices is usually denoted Kn, while the complete bipartite graph on two sets of m and n vertices is denoted Km,n. For example, 

K5 = {{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}},
K3,3 = {{1,4},{1,5},{1,6},{2,4},{2,5},{2,6},{3,4},{3,5},{3,6}}.

A walk of length n is a sequence v1e1v2e2...vnenvn+1 of vertices and edges such that each is incident to the next. It is closed if v1 = vn+1, and open otherwise. A trail is a walk in which all edges are distinct, a circuit is a closed trail with at least one edge. A path is a trail in which all vertices are distinct (except possibly v1 and vn+1 in a closed trail). A cycle is a circuit which does not contain a vertex twice (except at the beginning and end). An Euler's circuit is a walk that uses each edge of a graph exactly once. 

Two vertices are connected if there is a walk from one to the other. The relation of vertex connectivity is a relation of equivalence (reflexive, symmetrical and transitive). As such it induces a partition of the set of vertices V(G) into equivalence classes called connected components (or just components) of G. A graph is connected if there is just one equivalence class, that is, if every pair of vertices is connected. A tree is a connected graph with no cycles. 

The vertex connectivity k(G) of a graph G is the minimum number of vertices you need to remove (together with the incident edges) in order to disconnect the graph (or to reduce it to a 1-vertex graph, in the case when G cannot be disconnected by removing vertices). A graph is called k-vertex connected (or just k-connected) if it requires the removal of at least k vertices to disconnect the graph, or to make it a 1-vertex graph. 

A connected graph G is k-edge connected, if it requires the removal of at least k edges to disconnect the graph. The edge connectivity of a graph G is the minimum number of edges you need to delete in order to disconnect the graph. 
 
 

PreviousContentsNext