Adjacency

Introduction

An edge connects two vertices; these two vertices are said to be incident to that edge, or, equivalently, that edge incident to those two vertices. Two vertices u and v are called adjacent if they share a common edge {u, v} or uv. Two edges {u, v} and {v, w} of a graph are called adjacent if they share a common vertex v. For graph G(V, E):

If edge e = {u, v} ∈ E(G), we say that u and v are adjacent or neighbours. u and v are incident with e

u and v are end-vertices of e

An edge where the two end vertices are the same is called a loop, or a self-loop

The set of neighbours of v, that is, vertices adjacent to v not including v itself, forms an induced subgraph called the (open) neighbourhood of v and denoted NG(v). When v is also included, it is called a closed neighbourhood and denoted by NG[v]. When stated without any qualification, a neighbourhood is assumed to be open. The subscript G is usually dropped when there is no danger of confusion; the same neighbourhood notation may also be used to refer to sets of adjacent vertices rather than the corresponding induced subgraphs. For a simple graph, the number of neighbours that a vertex has coincides with its degree.

Form

Adjacency is denoted by u ~ v.