Graphs

Vertices, edges, paths, degrees, and network structure.

In discrete mathematics, a graph is not the graph of a function. It is a network made of objects and connections. Graphs model roads, friendships, links, prerequisites, dependencies, and communication networks.

Learning objectives

After this lesson you should be able to:

  • define vertices and edges;
  • distinguish directed and undirected graphs;
  • compute vertex degrees;
  • identify walks, paths, and cycles;
  • decide whether a small graph is connected;
  • represent a graph with an edge list or adjacency list.

Vertices and edges

A vertex is a node or object. An edge is a connection between vertices.

Example edge list:

V = {A, B, C, D}
E = {AB, AC, BC, CD}

This graph has four vertices and four edges.

Directed and undirected graphs

In an undirected graph, an edge AB connects A and B both ways. In a directed graph, an edge has a direction, such as A -> B.

Directed graphs model one-way streets, web links, task dependencies, and follower relationships.

Degree

In an undirected graph, the degree of a vertex is the number of edges incident to it.

For edges AB, AC, BC, CD:

  • degree of A is 2;
  • degree of B is 2;
  • degree of C is 3;
  • degree of D is 1.

Handshake idea

In an undirected graph, the sum of all degrees equals twice the number of edges, because each edge touches two endpoints.

Walks, paths, and cycles

A walk is a sequence of vertices where consecutive vertices are connected. A path is a walk with no repeated vertices. A cycle starts and ends at the same vertex without repeating other vertices.

Different textbooks vary slightly in advanced definitions, but these beginner versions are enough for this lesson.

Connected graphs

An undirected graph is connected if every vertex can be reached from every other vertex by following edges.

An isolated vertex with no edges can make a graph disconnected.

Representations

A graph can be represented by:

  • a drawing;
  • an edge list;
  • an adjacency list;
  • an adjacency matrix.

Adjacency list for edges AB, AC, BC, CD:

A: B, C
B: A, C
C: A, B, D
D: C

Worked example 1: degree sequence

For edges AB, AC, BC, CD, the degrees are:

deg(A)=2
deg(B)=2
deg(C)=3
deg(D)=1

The degree sequence is usually written from largest to smallest:

3, 2, 2, 1

Worked example 2: path or not?

In the same graph, A, B, C, D is a path because each consecutive pair is connected and no vertex repeats.

The sequence A, B, A, C is a walk, but not a path, because vertex A repeats.

Worked example 3: real model

Suppose courses are vertices and an arrow A -> B means course A must be taken before course B. This directed graph helps identify valid course orders and prerequisite chains.

Common pitfalls

  • Confusing graph theory networks with function graphs.
  • Counting a directed edge as if it automatically goes both ways.
  • Double-counting or under-counting degrees.
  • Forgetting isolated vertices when checking connectedness.
  • Calling any walk a path even when vertices repeat.

Practice

  1. For edges AB, AC, BC, CD, find degree of C.
  2. Is A, B, C, D a path in that graph?
  3. Is A, B, A, C a path?
  4. Give one real-world example of a directed graph.
  5. What does connected mean?
  1. 3.
  2. Yes.
  3. No. Vertex A repeats, so it is a walk but not a path.
  4. Web links, one-way roads, prerequisites, or follower relationships.
  5. Every vertex can be reached from every other vertex.

Subtopic guided practice and checkpoints

Graph theory problems are easiest when you translate every word into vertices, edges, and movement rules.

Lab 1: identify vertices and edges

Guess first. If V = {A, B, C} and E = {AB, BC}, which vertices are adjacent to B?

Guided exercise.

An edge touches its endpoints. Since AB touches A and B, and BC touches B and C, vertex B is adjacent to both A and C.

Checkpoint. For V = {1, 2, 3, 4} and E = {12, 14, 23}, list the neighbors of vertex 1.

Lab 2: compute degrees and check the handshake rule

Guess first. For edges AB, AC, BC, CD, which vertex has the largest degree?

Guided exercise.

Count how many edges touch each vertex:

deg(A) = 2  from AB, AC
deg(B) = 2  from AB, BC
deg(C) = 3  from AC, BC, CD
deg(D) = 1  from CD

The degree sum is 2 + 2 + 3 + 1 = 8, which equals 2 * 4 edges. This checks the handshake rule.

Checkpoint. For edges AB, AD, BD, CD, compute every degree and check the degree-sum formula.

Lab 3: distinguish walks, paths, and cycles

Guess first. Is A, B, A, C a path?

Guided exercise.

A walk only needs consecutive vertices to be connected. A path cannot repeat vertices. A, B, A, C repeats A, so it may be a walk, but it is not a path.

A cycle starts and ends at the same vertex while avoiding repeated internal vertices.

Checkpoint. In a graph with edges AB, BC, CD, DA, classify A, B, C, D, A as a walk, path, cycle, or more than one of these.

Lab 4: choose a representation

Guess first. Which representation is better for checking neighbors quickly: an edge list or an adjacency list?

Guided exercise.

Edge lists are compact:

AB, AC, BC, CD

Adjacency lists make neighbors obvious:

A: B, C
B: A, C
C: A, B, D
D: C

Checkpoint. Convert the edge list AB, AC, CD into an adjacency list. Is the graph connected?

  1. Vertex 1 is adjacent to 2 and 4.
  2. For edges AB, AD, BD, CD, the degrees are deg(A)=2, deg(B)=2, deg(C)=1, and deg(D)=3. The degree sum is 8, which equals twice the number of edges.
  3. A, B, C, D, A is a walk and a cycle. It is not a path under the beginner definition because the starting vertex repeats at the end.
  4. The adjacency list is A: B, C, B: A, C: A, D, D: C. The graph is connected.

Graphs checkpoint

Using this lesson with edumath and SymPy

Use edumath graph helpers for small finite graphs.

from edumath.discrete_math import degree, degree_sequence, is_connected, is_path, neighbors

vertices = ("A", "B", "C", "D")
edges = (("A", "B"), ("A", "C"), ("B", "C"), ("C", "D"))

degree(vertices, edges, "C"), degree_sequence(vertices, edges)
(3, (3, 2, 2, 1))
neighbors(vertices, edges, "A"), is_path(vertices, edges, ("A", "B", "C", "D")), is_connected(vertices, edges)
({'B', 'C'}, True, True)

SymPy is not the main tool for introductory graph theory. For larger graph projects, a specialized library such as NetworkX is useful, but this lesson uses small built-in helpers to keep the ideas transparent.