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 K_{n}, while the complete bipartite graph on two sets of m and n vertices is denoted K_{m,n}. For example,
A walk of length n is a sequence v_{1}e_{1}v_{2}e_{2}...v_{n}e_{n}v_{n+1} of vertices and edges such that each is incident to the next. It is closed if v_{1} = v_{n+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 v_{1} and v_{n+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 1vertex graph, in the case when G cannot be disconnected by removing vertices). A graph is called kvertex connected (or just kconnected) if it requires the removal of at least k vertices to disconnect the graph, or to make it a 1vertex graph. A connected graph G is
kedge 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.
