Course contentsShow
← Mathematics
Lesson 2651 of 3,12153. Graph TheoryFree lesson

Adjacency and Incidence

Define when two vertices are adjacent, when a vertex and edge are incident, and introduce neighborhood notation.

Adjacency and Incidence

You'll learn how to describe the fundamental relationships between vertices and edges in a graph using precise terminology.

Now that you know what vertices and edges are, let's talk about how they relate to each other with formal language. These relationships form the vocabulary for all graph theory work.

Adjacent Vertices

Two vertices are adjacent (or neighbors) if there is an edge connecting them directly. Think of adjacency like being "next-door neighbors" in a network—you're connected by a single link.

For example, if we have vertices u and v with an edge e = {u, v} between them, then u and v are adjacent.

Incidence

A vertex and an edge are incident if the vertex is one of the endpoints of that edge. Another way to think about it: the edge "touches" or "attaches to" that vertex.

Using the same example, vertex u is incident to edge e, and vertex v is also incident to edge e.

Neighborhood Notation

The neighborhood of a vertex v, denoted N(v), is the set of all vertices adjacent to v. This is incredibly useful for describing local structure in a graph.

For instance, if vertex a is connected to vertices b, c, and d, then:

  • N(a) = {b, c, d}

The degree of vertex a (which you learned earlier) equals |N(a)|—the size of its neighborhood.

Analogy

Think of a social network: you are adjacent to your direct friends, you and your friendships are incident (you're an endpoint of each friendship), and your neighborhood is your entire friend list.

Key Takeaway: Adjacent vertices share an edge; incident means a vertex and edge are connected; the neighborhood N(v) collects all vertices adjacent to v.