Definition: Incidence, Adjacency, Neighbours

Let \(G=(V,E,\gamma)\) be an undirected graph. A vertex \(v\in V\) and an edge \(e\in E\) are called incident if \(v\in\gamma(e)\).

Two different edges \(e,e'\in E\) are called adjacent, if there is at least one vertex incident with these edges, formally \( e\neq e'\) and \(\exists v:~ v\in \gamma(e) \cap \gamma(e') \).

Two different vertices \(v,v'\in V\) are neighbours or are called adjacent, if there is at at least one edge incident with these vertices, formally \( v\neq v'\) and \(\exists e:~v,v'\in \gamma(e) \).

Let \(v\in V\) be a vertex of \(G\). (Note: In the following definitions, the index \(D\) can be omitted in the notation, if it is clear from the context, which digraph \(G\) is concerned).

The set \(\delta_G(v):=\{e\in E: v\in \gamma(e)\}\) is called edges incident to v.

The set \(N_G(v):=\{x\in V: x\in \delta_G(v)\}\) is called neighbors of v.

Example:

graphs6

The values of the degrees of vertices in the above graph are:

Vertex \(v\) Neighbours \(N(v)\)
\(a\) \(\{b,c,d\}\)
\(b\) \(\{a,c\}\)
\(c\) \(\{a,b\}\)
\(d\) \(\{a,e\}\)
\(e\) \(\{d,e\}\)
\(f\) \(\emptyset\)

Definitions: 1 2 3 4


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs