Adjacency and Incidence

Adjacency of Vertices

Definition: For a graph $G = (V(G), E(G))$, two vertices $x, y \in V(G)$ are said to be Adjacent if they are connected by an edge. That is $\{ x, y \} \in E(G)$

For example, let's look at the following graph:

Let's first look at vertex $a$. Vertex $a$ is adjacent to vertex $b$, vertex $c$, and vertex $d$ since $\{a, b \}, \{a, c \}, \{a, d \} \in E(G)$.

Now let's look at vertex $d$. Vertex $d$ is NOT adjacent to vertex $e$ and $\{ d, e \} \not \in E(G)$. However, vertex $d$ is adjacent to vertex $a$ and vertex $c$ since $\{a, d \}, \{ c, d \} \in E(G)$.

Incidence of a Vertex / Edge

Definition: For a graph $G = (V(G), E(G))$, two vertices $x, y \in V(G)$ which are adjacent forming an edge $\{ x, y \}$ are said to be Incident to that edge. Alternatively, the edge $\{ x, y \}$ is also incident to the vertices $x$ and $y$.

From the graph above, we can say that the edge $ad$ is incident to vertices $a$ and $d$. We can also say that vertex $a$ is incident to edge $ad$, and vertex $d$ is incident to edge $ad$.