nonadjacency

In graph theory, nonadjacency is the relation between two vertices that are not joined by an edge. If two distinct vertices u and v are nonadjacent, there is no edge {u,v} in the graph.

Formally, in a simple graph G = (V, E), two distinct vertices u and v are nonadjacent when {u, v} ∉ E. For a vertex v, the set of its nonneighbors is the complement of its closed neighborhood: N̄(v) = V \ ({v} ∪ N(v)), where N(v) is the set of vertices adjacent to v.

Nonadjacency is closely related to the concept of a complement graph. The complement graph Ḡ has the same vertex set V, and edge set Ē consisting of all pairs {u, v} that are not edges in G. Thus, two vertices that are nonadjacent in G are adjacent in Ḡ, and vice versa.

Examples help illustrate the idea. In a square cycle C4, opposite vertices are nonadjacent. In a triangle K3, every pair of vertices is adjacent, so there are no nonadjacent pairs. In a path P3 with vertices a–b–c, a and c are nonadjacent.

Applications of nonadjacency appear in several areas of graph theory. The independence number α(G) is the size of the largest set of pairwise nonadjacent vertices. Nonadjacency constraints also underlie graph coloring, where adjacent vertices must have different colors while nonadjacent vertices may share a color. Adjacency and nonadjacency matrices provide binary representations of these relations, with 1s indicating adjacency or nonadjacency as appropriate.

See also: adjacency, complement graph, independence number, graph coloring, nonedges.