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,
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.