Year 12 Graph Theory: Adjacency and incidence

Adjacency and incidence are two of the most useful words in graph theory, and they are often mixed up by students because they both describe connections. The difference is that adjacency usually compares two vertices, while incidence compares a vertex and an edge. Once that distinction is clear, graph descriptions become much more precise. This matters because many matrix models, vertex properties, and route questions rely on understanding exactly what kind of connection is being described.

Vertices are adjacent to vertices. Edges are incident with vertices. Keeping those roles separate makes the rest of graph theory much cleaner.

Subtopic 1: Adjacency between vertices

Two vertices are adjacent if an edge directly joins them. Adjacency tells you immediate one-step connection, not overall reachability. This is an important distinction because two vertices may lie in the same connected component but still fail to be adjacent if they are only linked through intermediate vertices.

Worked example 1

Problem: In a graph, edges

A B

B C

, and

C D

exist. Are vertices

A

and

C

adjacent?

Adjacency requires a direct edge between the two vertices.
There is no edge $A C$ .
Although $A$ can reach $C$ through $B$ , that is not direct adjacency.

Answer: no,

A

and

C

are not adjacent.

Subtopic 2: Incidence between vertices and edges

An edge is incident with the vertices at its ends. Incidence is therefore about the relationship between an edge and a vertex, not two vertices. This concept is useful when counting degree, describing edge structure, or building incidence-style representations of a graph. If the edge $A B$ exists, then it is incident with vertex $A$ and also incident with vertex $B$ .

Worked example 2

Problem: Edge

E F

appears in a graph. Which vertices is it incident with?

An edge is incident with its endpoint vertices.
The endpoints of $E F$ are $E$ and $F$ .

Answer: edge

E F

is incident with vertices

E

and

F

Why the distinction matters

Adjacency and incidence look close enough that students sometimes treat them as interchangeable. That causes problems later, especially when the graph is being converted into an adjacency matrix, when degrees are counted, or when a question asks for a precise network description. Graph theory depends on clean language. If you know exactly whether the question is talking about vertex-vertex connection or edge-vertex attachment, the interpretation becomes much more reliable.

Worked example 3

Problem: Explain why the statement "edge

A B

is adjacent to vertex

A

" is poor graph-theory language.

Adjacency is usually used to compare two vertices.
The correct relation between an edge and a vertex is incidence.
So the accurate statement is that edge $A B$ is incident with vertex $A$ .

Answer: the correct word is

incident

, not

adjacent

Links to matrices and structure

This distinction also supports later discrete-mathematics ideas. An adjacency matrix records which vertices are adjacent, while other matrix models may encode different relationships altogether. If you already understand what adjacency means in the graph itself, those matrix representations become more meaningful. The same is true for degree, since degree counts the number of incident edges at a vertex.

Common traps

Saying two vertices are adjacent when they are only connected through a path.
Using adjacency language for an edge-vertex relationship.
Thinking incidence compares two edges rather than an edge and a vertex.
Failing to connect degree with the count of incident edges.

Revision focus

One effective revision method is to write short graph statements and classify each as adjacency, incidence, degree, or path language. That builds fluency in the vocabulary, which is often what separates clean graph-theory solutions from vague ones. The arithmetic is usually easy once the relationships are described correctly.

It also helps to annotate diagrams with both edges and vertices clearly named. Once the labels are in place, it becomes much easier to test statements such as "A is adjacent to B" or "edge CD is incident with D" directly from the picture without relying on memory or guesswork.