The Central Idea
A graph records which objects are connected to which other objects.
We usually write a graph as
\[ \boxed{G=(V,E)}, \]where \(V\) is the set of vertices and \(E\) is the set of edges.
The geometry of the drawing is usually secondary. The essential information is the connection structure.
What Is a Vertex?
A vertex is one of the objects represented in a graph. The plural is vertices.
Vertices may represent people, cities, web pages, tasks, computers, intersections, states of a system, or almost any other collection of discrete objects.
A set of four vertices might be written
\[ V=\{a,b,c,d\}. \]What Is an Edge?
An edge represents a relationship or connection between vertices.
In an undirected graph, an edge joining \(a\) and \(b\) can be written
\[ \{a,b\}. \]The order does not matter:
\[ \{a,b\}=\{b,a\}. \]Directed edges will be treated in the next lesson.
A First Graph
Consider the graph
\[ V=\{a,b,c,d\} \]with edge set
\[ E=\bigl\{\{a,b\},\{a,c\},\{b,c\},\{c,d\}\bigr\}. \]This means that \(a\) is connected to \(b\) and \(c\), \(b\) is connected to \(a\) and \(c\), and \(d\) is connected only to \(c\).
A Graph as a Picture
The same graph can be drawn visually. The positions of the vertices are chosen for readability; they are not coordinates unless the problem explicitly gives them geometric meaning.
Graph Drawings Are Flexible
A graph is not defined by one particular picture. We may move vertices, bend edges, or redraw the graph without changing the graph, provided the same vertices remain connected.
For example, these edge relationships
\[ \{a,b\},\qquad \{a,c\},\qquad \{b,c\},\qquad \{c,d\} \]describe the same abstract graph no matter where the four vertex symbols are placed on the page.
Endpoints of an Edge
If an edge joins vertices \(u\) and \(v\), then \(u\) and \(v\) are called the endpoints of that edge.
For
\[ e=\{u,v\}, \]the endpoints of \(e\) are \(u\) and \(v\).
Adjacency between Vertices
Two vertices are adjacent when an edge joins them.
In the graph
\[ E=\bigl\{\{a,b\},\{a,c\},\{b,c\},\{c,d\}\bigr\}, \]\(a\) and \(b\) are adjacent because \(\{a,b\}\in E\).
The vertices \(a\) and \(d\) are not adjacent because
\[ \{a,d\}\notin E. \]Adjacency Is a Local Relationship
Adjacency asks whether two vertices are connected by one edge.
It does not ask whether one vertex can eventually be reached from another through several edges. That broader idea leads to paths and connectivity, which will be developed later in this chapter.
Incidence
A vertex and an edge are incident when the vertex is an endpoint of the edge.
If
\[ e=\{a,c\}, \]then \(e\) is incident with \(a\) and \(c\).
The edge \(e\) is not incident with \(b\) or \(d\).
Adjacency and Incidence Are Different
The words describe two different kinds of relationships.
- Adjacency usually compares vertex to vertex.
- Incidence compares a vertex to an edge.
Thus, if \(e=\{u,v\}\), then \(u\) and \(v\) are adjacent, while \(u\) is incident with \(e\) and \(v\) is incident with \(e\).
Naming Edges
Sometimes an edge is identified only by its endpoints:
\[ \{u,v\}. \]In other settings, edges are given their own names such as
\[ e_1,e_2,e_3. \]Named edges become especially useful when several edges must be tracked explicitly.
Simple Graphs
A simple graph has no loops and no multiple edges between the same pair of vertices.
In a simple undirected graph, each edge can therefore be identified by a two-element set
\[ \{u,v\},\qquad u\ne v. \]Unless another graph type is specified, introductory examples often use simple graphs.
Loops and Multiple Edges
Some graph models allow structures that simple graphs exclude.
A loop is an edge whose two ends meet the same vertex. Some graph models also allow more than one edge between the same pair of vertices.
Because conventions vary across graph types, always identify the type of graph before applying counting rules.
The Neighborhood of a Vertex
The neighborhood of a vertex \(v\), often written \(N(v)\), is the set of vertices adjacent to \(v\).
In our running graph,
\[ N(a)=\{b,c\}, \] \[ N(c)=\{a,b,d\}, \]and
\[ N(d)=\{c\}. \]Degree of a Vertex
In a simple undirected graph, the degree of a vertex is the number of edges incident with that vertex.
We write the degree of \(v\) as
\[ \deg(v). \]Equivalently, in a simple graph,
\[ \boxed{\deg(v)=|N(v)|}. \]Example: Finding Degrees
For
\[ E=\bigl\{\{a,b\},\{a,c\},\{b,c\},\{c,d\}\bigr\}, \]the vertex degrees are
\[ \deg(a)=2, \] \[ \deg(b)=2, \] \[ \deg(c)=3, \]and
\[ \deg(d)=1. \]Isolated Vertices
An isolated vertex has degree \(0\).
If \(x\in V\) but no edge has \(x\) as an endpoint, then
\[ \boxed{\deg(x)=0}. \]The vertex is still part of the graph even though it is not joined to any other vertex.
Leaf or Pendant Vertices
A vertex of degree \(1\) is often called a leaf or pendant vertex.
In the running graph, \(d\) is a leaf because
\[ \deg(d)=1. \]This language becomes especially important when studying trees.
Counting Incidences
Every ordinary undirected edge has two endpoints. Therefore each edge contributes \(2\) to the total of all vertex degrees.
For a finite undirected graph,
\[ \boxed{\sum_{v\in V}\deg(v)=2|E|}. \]This relationship is often called the handshaking lemma.
Example: Checking the Degree Sum
Our running graph has four edges, so
\[ 2|E|=2(4)=8. \]The degrees add to
\[ 2+2+3+1=8. \]The two counts agree because both count the same vertex-edge incidences.
Why the Degree Sum Must Be Even
Since
\[ \sum_{v\in V}\deg(v)=2|E|, \]the sum of all vertex degrees in a finite undirected graph must be even.
This gives a quick consistency check for proposed degree data.
Odd-Degree Vertices Come in Pairs
An important consequence is that every finite undirected graph has an even number of vertices of odd degree.
In the running example, the odd-degree vertices are
\[ c\quad\text{and}\quad d, \]so there are two of them.
Edge Sets Encode the Graph
A graph can be described without drawing it. If
\[ V=\{1,2,3,4,5\} \]and
\[ E=\bigl\{\{1,2\},\{1,4\},\{2,4\},\{3,5\}\bigr\}, \]then the graph is determined by these sets, assuming the graph type is understood.
Adjacency Lists
An adjacency list records the neighbors of each vertex.
For the graph
\[ E=\bigl\{\{a,b\},\{a,c\},\{b,c\},\{c,d\}\bigr\}, \]an adjacency list is
- \(a:\ b,c\)
- \(b:\ a,c\)
- \(c:\ a,b,d\)
- \(d:\ c\)
Reading Degree from an Adjacency List
For a simple undirected graph, the number of entries in a vertex's adjacency list is its degree.
Since
\[ c:\ a,b,d, \]we immediately read
\[ \deg(c)=3. \]Adjacency Matrices
A finite graph can also be represented by an adjacency matrix.
For vertices \(v_1,\ldots,v_n\), define
\[ A_{ij}= \begin{cases} 1,&\text{if }v_i\text{ and }v_j\text{ are adjacent},\\ 0,&\text{otherwise}. \end{cases} \]For a simple undirected graph, the matrix is symmetric across its main diagonal.
Example: Adjacency Matrix
Using vertex order \(a,b,c,d\), our running graph has adjacency matrix
\[ A= \begin{pmatrix} 0&1&1&0\\ 1&0&1&0\\ 1&1&0&1\\ 0&0&1&0 \end{pmatrix}. \]The \(1\) in row \(a\), column \(c\) records the edge \(\{a,c\}\). The \(0\) in row \(a\), column \(d\) records that \(a\) and \(d\) are not adjacent.
Degree from an Adjacency Matrix
In a simple undirected graph, the degree of a vertex equals the sum of the entries in its row.
The row for \(c\) is
\[ (1,1,0,1), \]whose entries sum to
\[ 1+1+0+1=3. \]Therefore,
\[ \deg(c)=3. \]Incidence Tables
When edges are named, we can record which vertices are incident with which edges.
Let
\[ e_1=\{a,b\},\quad e_2=\{a,c\},\quad e_3=\{b,c\},\quad e_4=\{c,d\}. \]Then an incidence table is
| Vertex | \(e_1\) | \(e_2\) | \(e_3\) | \(e_4\) |
|---|---|---|---|---|
| \(a\) | 1 | 1 | 0 | 0 |
| \(b\) | 1 | 0 | 1 | 0 |
| \(c\) | 0 | 1 | 1 | 1 |
| \(d\) | 0 | 0 | 0 | 1 |
Reading an Incidence Table
In a simple undirected graph, each edge column contains exactly two \(1\)s because every edge has two distinct endpoints.
A row sum gives the degree of the corresponding vertex.
The row for \(c\) contains three \(1\)s, so
\[ \deg(c)=3. \]Three Views of the Same Graph
A graph can be represented in several equivalent ways:
- as a drawing;
- as a vertex set and edge set;
- as adjacency lists;
- as an adjacency matrix;
- as an incidence table or incidence matrix.
Each representation emphasizes different information, but all may describe the same underlying graph.
Example: From a Verbal Description to a Graph
Suppose four departments are labeled \(A,B,C,D\). Direct collaboration exists between \(A\) and \(B\), \(A\) and \(C\), \(B\) and \(D\), and \(C\) and \(D\).
We may model the departments as
\[ V=\{A,B,C,D\} \]and the collaborations as
\[ E= \bigl\{ \{A,B\},\{A,C\},\{B,D\},\{C,D\} \bigr\}. \]Example: Reading Adjacency from Data
For
\[ E= \bigl\{ \{A,B\},\{A,C\},\{B,D\},\{C,D\} \bigr\}, \]the neighborhood of \(A\) is
\[ N(A)=\{B,C\}. \]The vertices \(B\) and \(C\) are both adjacent to \(A\), but they are not adjacent to each other unless \(\{B,C\}\) is also included in the edge set.
Example: Reading Incidence from Data
Let
\[ e=\{B,D\}. \]Then \(B\) and \(D\) are the endpoints of \(e\), so both are incident with \(e\).
The vertices \(A\) and \(C\) are not incident with \(e\).
Graph Structure versus Labels
Labels help us discuss individual vertices, but many graph questions depend on structure rather than on the particular names chosen.
Relabeling
\[ a,b,c,d \]as
\[ 1,2,3,4 \]does not change the pattern of connections if the same adjacency relationships are preserved.
Graph Structure versus Physical Distance
Two vertices drawn close together need not be adjacent, and vertices drawn far apart may be adjacent.
An edge, not visual distance, determines adjacency.
This distinction is essential when reading network diagrams.
Common Error: Treating Edge Crossings as Vertices
When two drawn edges cross, the crossing point is not automatically a vertex.
A crossing represents a vertex only if the graph explicitly marks or defines a vertex there.
Graph drawings can therefore contain visual intersections that do not represent additional adjacency or incidence.
Common Error: Confusing Adjacent with Reachable
Suppose \(a\) is adjacent to \(b\), and \(b\) is adjacent to \(c\).
It does not follow that \(a\) is adjacent to \(c\).
Adjacency requires a direct edge:
\[ \{a,c\}\in E. \]Common Error: Forgetting a Vertex with Degree Zero
If
\[ V=\{a,b,c,d\} \]and
\[ E=\bigl\{\{a,b\},\{b,c\}\bigr\}, \]then \(d\) is still part of the graph.
It is simply isolated:
\[ \deg(d)=0. \]Common Error: Counting Every Neighbor Twice
If \(N(v)=\{a,b,c\}\), then
\[ \deg(v)=3, \]not \(6\).
The handshaking lemma doubles the total number of edges only when degrees are summed across all vertices.
Common Error: Assuming the Drawing Defines the Graph
A graph may be redrawn without changing its abstract structure.
Angles, lengths, slopes, and exact positions are irrelevant unless those quantities are explicitly part of the model.
Focus first on which vertices are joined.
A Reliable Procedure for Reading a Graph
- Identify the vertex set \(V\).
- Identify the edge set \(E\).
- For each edge, identify its endpoints.
- Use the edges to determine which vertices are adjacent.
- Use endpoints to determine vertex-edge incidence.
- Build neighborhoods when useful.
- Count incident edges to determine degrees.
- Check degree totals against \(2|E|\) for a finite undirected graph.
Example: Full Reading Workflow
Let
\[ V=\{p,q,r,s,t\} \]and
\[ E= \bigl\{ \{p,q\}, \{p,r\}, \{q,r\}, \{r,s\}, \{s,t\} \bigr\}. \]Then
\[ N(r)=\{p,q,s\}, \]so
\[ \deg(r)=3. \]The complete degree list is
\[ \deg(p)=2,\quad \deg(q)=2,\quad \deg(r)=3,\quad \deg(s)=2,\quad \deg(t)=1. \]The sum is
\[ 2+2+3+2+1=10=2(5)=2|E|. \]Why This Language Matters
Vertices and edges are the basic objects from which the rest of graph theory is built.
Adjacency and incidence will support later ideas involving:
- paths and connectivity;
- trees and spanning trees;
- Eulerian and Hamiltonian problems;
- graph coloring;
- shortest-path algorithms;
- network flow;
- bipartite matching;
- social and infrastructure networks.
Practice 1: Identify Vertices and Edges
Let
\[ G=(V,E), \]where
\[ V=\{a,b,c,d,e\} \]and
\[ E= \bigl\{ \{a,b\},\{a,d\},\{b,c\},\{c,d\} \bigr\}. \]How many vertices and how many edges does \(G\) have?
Practice 2: Adjacency
Using the graph from Practice 1, list all vertices adjacent to \(a\).
Practice 3: Nonadjacency
Using the same graph, are \(b\) and \(d\) adjacent? Explain using the edge set.
Practice 4: Incidence
Let
\[ e_1=\{a,d\}. \]Which vertices are incident with \(e_1\)?
Practice 5: Neighborhood
For
\[ E= \bigl\{ \{a,b\},\{a,d\},\{b,c\},\{c,d\} \bigr\}, \]find \(N(c)\).
Practice 6: Degree
Find
\[ \deg(a),\quad \deg(b),\quad \deg(c),\quad \deg(d),\quad \deg(e). \]Practice 7: Degree-Sum Check
Verify that the degree sum from Practice 6 equals \(2|E|\).
Practice 8: Adjacency List
Write a complete adjacency list for
\[ V=\{1,2,3,4\} \]and
\[ E= \bigl\{ \{1,2\},\{1,3\},\{2,4\} \bigr\}. \]Practice 9: Adjacency Matrix
Using vertex order \(1,2,3,4\), write the adjacency matrix for the graph in Practice 8.
Practice 10: Identify the Error
A student says that vertices \(u\) and \(w\) are adjacent because the graph contains the edges
\[ \{u,v\} \]and
\[ \{v,w\}. \]Explain the error.
Practice Answers
Practice 1
There are five vertices and four edges:
\[ \boxed{|V|=5,\qquad |E|=4}. \]Practice 2
The edges incident with \(a\) are \(\{a,b\}\) and \(\{a,d\}\), so
\[ \boxed{N(a)=\{b,d\}}. \]Practice 3
No. The edge set does not contain \(\{b,d\}\), so
\[ \boxed{b\text{ and }d\text{ are not adjacent}}. \]Practice 4
The endpoints of \(e_1=\{a,d\}\) are \(a\) and \(d\). Therefore,
\[ \boxed{a\text{ and }d\text{ are incident with }e_1}. \]Practice 5
The edges containing \(c\) are \(\{b,c\}\) and \(\{c,d\}\). Thus,
\[ \boxed{N(c)=\{b,d\}}. \]Practice 6
Count the incident edges at each vertex:
\[ \boxed{ \deg(a)=2,\quad \deg(b)=2,\quad \deg(c)=2,\quad \deg(d)=2,\quad \deg(e)=0 }. \]Practice 7
The degree sum is
\[ 2+2+2+2+0=8. \]Since \(|E|=4\),
\[ 2|E|=2(4)=8. \]Therefore,
\[ \boxed{\sum_{v\in V}\deg(v)=2|E|}. \]Practice 8
The adjacency list is
- \(1:\ 2,3\)
- \(2:\ 1,4\)
- \(3:\ 1\)
- \(4:\ 2\)
Practice 9
Using order \(1,2,3,4\),
\[ \boxed{ A= \begin{pmatrix} 0&1&1&0\\ 1&0&0&1\\ 1&0&0&0\\ 0&1&0&0 \end{pmatrix} }. \]Practice 10
The two given edges show that \(u\) is adjacent to \(v\) and that \(v\) is adjacent to \(w\).
They do not establish adjacency between \(u\) and \(w\). That would require
\[ \boxed{\{u,w\}\in E}. \]What to Remember
A graph is built from a vertex set and an edge set:
\[ \boxed{G=(V,E)}. \]- Vertices represent objects.
- Edges represent relationships between vertices.
- Adjacent vertices share an edge.
- A vertex is incident with an edge when it is one of the edge's endpoints.
- The neighborhood \(N(v)\) contains the vertices adjacent to \(v\).
- In a simple undirected graph, \(\deg(v)=|N(v)|\).
- For a finite undirected graph, \(\sum_{v\in V}\deg(v)=2|E|\).
- A graph's structure depends on connections, not on the exact geometry of its drawing.
Where We Go Next
This lesson treated edges as symmetric connections: an edge joining \(u\) and \(v\) did not distinguish one endpoint as the starting point and the other as the destination.
The next lesson, Directed and Undirected Graphs, introduces orientation and shows how graph structure changes when relationships have direction.