-
Empty Graph - the graph with no vertices.
-
Null Graph -
- the graph with no edges. -
Complete Graph -
- the graph where each pair of distinct vertices is adjacent. -
Bipartite Graph - it is possible to split the vertex set into two disjoint sets called the bipartition
such that each edge is of the form is bipartite if it can be expressed as the union of disjoint, possibly empty independent sets is -colorable. - (Wilson 5.1)
is bipartite if and only if every cycle has even length.
-
Complete Bipartite Graph -
given the bipartition of the bipartite graph. , all vertices from are adjacent to all vertices in . Here
-
A regular graph is a graph where the degree of each vertex in the graph is equal. If each vertex has degree
, then the graph is -regular. More formally, if
is the -regular graph then -
Cubic Graph - a
-regular graph. -
A cycle of
vertices is denoted