A graph \(G\) is an ordered triple \((V(G), E(G), \psi_{G})\) consisting of a nonempty set \(V(G)\) of vertices, a set \(E(G)\), disjoint from \(V(G)\), of edges, and an incidence function \(\psi_{G}\) that associates each edge of \(G\) an undordered pair of (not necessarily distinct) vertices of \(G\). If \(e\) is an edge and \(u,v\) vertices such that \(\psi_{G}(e) = uv\), then \(e\) is said to join \(u\) and \(v\); the vertices \(u,v\) are called the ends of \(e\).

Planar graphs are graphs that can be diagramatically represented such that the edges of the graph only intersect at the vertices of the graph are called planar.

The ends of an edge are said to be incident with the edge, and vice versa. Two vertices which are incident with a common edge are adjacent, as are two edges which are incident with a common vertex. An edge with identical ends is called a loop, and an edge with distinct ends is a link.

A graph is finite if both its vertex set and edge set are finite. We call a graph with just one vertex trivial and all other graphs nontrivial.

A graph is simple if it has no loops and no two of its links join the same pair of vertices.

The symbols \(v(G), \epsilon (G)\) refer to the number of vertices, and the number of edges of the graph \(G\).

Two graphs \(G,H\) are said to be identical if \(V(G) = V(H), E(G) = E(H), \psi_G = \psi_H\). \(G,H\) are said to be isomorphic (written \(G\cong H\)) if there are bijections \(\theta : V(G) \rightarrow V(H)\),\( \phi : E(G) \rightarrow E(H) \) such that \(\psi_G(e) = uv\) if and only if \(\psi_H(\phi(e)) = \theta (u)\theta (v)\); such a pair \(\theta,\phi\) is called an isomorphism between \(G\) and \(H\).

A complete graph is a simple graph where each pair of distinct vertices is joined by an edge. Up to isomorphism, there is just one complete graph on \(n\) vertices; it is denoted \(K_n\). An empty graph is a graph with no edges. A bipartite graph is one whose vertex set can be partitioned into two subsets \(X\) and \(Y\), so that each edge has one end in \(X\) and one end in \(Y\); such a partition \((X,Y)\) is called a bipartition of the graph. A complete bipartite graph is a simple bipartite graph with bipartition \((X,Y)\) in which each vertex of \(X\) is joined to each vertex of \(Y\); if \(|X| = m\) and \(|Y| = n\), such a graph is denoted by \(K_{m,n}\).