Fundamentals of Computing: Graph Theory: Vertices, Edges, Paths and Cycles

Lesson overview

Use graph terminology to model connected systems.

CourseFundamentals of Computing

Topic strandGraph theory

Assessment styleDigital exam practice

EvidenceWorked answer plus justification

Starter: make the model explicit

Before reading the worked example, write down the objects involved, the claim being made and the notation you expect to use. This prevents the common error of calculating before modelling.

Learning objectives

Define vertices, edges, paths and cycles.
Distinguish directed and undirected graphs.
Model a computing problem as a graph.

Learning outcomes

By the end of this lesson, you can define vertices, edges, paths and cycles.
By the end of this lesson, you can distinguish directed and undirected graphs.
By the end of this lesson, you can model a computing problem as a graph.

Key vocabulary

What this lesson is about

Graph theory studies vertices and edges. Vertices represent objects; edges represent relationships or connections between those objects.

Paths, cycles and directed edges let us reason about routes, dependencies, links, communication and reachability in computing systems.

Terms, acronyms and named methods

These are the phrases and named techniques used in this lesson. Read this section before the worked example so the notation and examples have a clear meaning.

GraphMathematical structure. A set of vertices together with edges connecting pairs of vertices.

VertexGraph term. An object or point in a graph.

EdgeGraph term. A connection between vertices. In a directed graph, the connection has direction.

CycleGraph term. A path that starts and ends at the same vertex.

Formal notation and definitions

A graph is G = (V, E). For directed graphs, E \subseteq V \times V. A path is a sequence v₀, v₁, ..., vₖ with each required edge present.

How to read the symbols

$G=(V,E)$ A graph G with vertex set V and edge set E.

$E\subseteq V\times V$ For directed graphs, edges are ordered pairs of vertices.

pathA sequence of vertices where each consecutive pair is joined by an edge.

Use graph notation after defining what vertices and edges represent. The same drawing can model different systems depending on that choice.

Degree-level reasoning

Graph theory is a modelling discipline. The mathematical graph is not the network itself; it is a selected abstraction of entities and connections.

A strong graph answer states what vertices and edges represent before discussing paths, cycles, connectivity or traversal.

Do not stop at a correct-looking answer. State why the method is valid, whether the result depends on a hidden assumption, and what would count as a counterexample.

Worked formal model

This section shows the model, notation, calculation and interpretation as one worked answer. The notation is part of the reasoning, not decoration.

1. Context and objects

Web pages and hyperlinks form a directed graph: pages are vertices and links are directed edges.

Objects: the vertex set V, edge set E, a path sequence, and any cycle identified in the graph.

Model cue: Use a labelled graph with vertices as circles and edges as lines or arrows. Always state what vertices and edges represent.

2. Mathematical working

G=(V,E),\quad V=\{A,B,C\}

E=\{(A,B),(B,C),(C,A)\}

A,B,C,A\quad\text{is a directed cycle}

Plain text version

A graph is G = (V, E).
For directed graphs, E ⊆ V × V.
A path is a sequence v₀, v₁, ..., vₖ with each required edge present.

Worked use: If vertices are web pages and directed edges are hyperlinks, then a path represents a possible click sequence. A cycle means a user can return to a page by following links.

3. How to read the working

Read G = (V, E) as the whole graph: V names the vertices and E names the edges.
For directed graphs, each edge is an ordered pair, so (A, B) and (B, A) are different edges.
Read A, B, C, A as a cycle because each consecutive directed edge exists and the route returns to A.
Translate the cycle back into the model, such as a possible return route in a linked website or network.

4. Computing meaning and check

The graph model makes reachability and cycles precise. A path is a possible sequence through the system only after vertices and edges have been defined.

Now check: Model a small website as a directed graph and identify one path and one cycle.

Worked example

From scenario to formal reasoning

Scenario: Web pages and hyperlinks form a directed graph: pages are vertices and links are directed edges.

Method: Use the definitions and notation introduced above, then state what the result means in this computing scenario.

Reveal model answer

If vertices are web pages and directed edges are hyperlinks, then a path represents a possible click sequence. A cycle means a user can return to a page by following links.

Worked solution structure

How a strong answer should be written

Define: State the domain and the objects under discussion. For this lesson, begin from A graph is G = (V, E).
Apply: Use the relevant definition from graph theory; do not rely on the diagram, wording or intuition alone.
Check: Test a boundary case, counterexample candidate or representation limit.
Conclude: Write one sentence that connects the formal result back to the computing scenario.

Common misconception

A common mistake is drawing a network without defining what vertices and edges mean. The model is only useful when the mapping is explicit.

Guided practice

Model a three-page website as a directed graph with at least one path and one cycle.
Write the vertex set and edge set for the graph.
Identify a directed path and justify each edge in the path.
Explain what the cycle means in the website model.

Quick checks

1. In a web graph, directed edges can represent:

hyperlinks from one page to anotherthe number of paragraphs onlyfont sizes

2. A directed cycle means:

no path existsa path returns to its starting vertexall edges are undirected

Digital exam practice

Example exam task

Model a website with pages Home, Products and Help and links Home → Products, Products → Help and Help → Home. State V and E, identify a path and a cycle, and explain what each means in the website.

Notation toolkit

G=(V,E)

Means: a graph with vertex set V and edge set E

How to use: Use it before discussing paths or cycles.

(u,v)

Means: a directed edge from u to v

How to use: Use it when edge direction matters.

v_0\to v_1\to\cdots\to v_k

Means: a path through consecutive edges

How to use: Use it when justifying reachability.

What a good answer is expected to show

A strong answer for this lesson defines the vertex set V, edge set E, a path sequence, and any cycle identified in the graph, applies the graph theory method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

Read G = (V, E) as the whole graph: V names the vertices and E names the edges.
For directed graphs, each edge is an ordered pair, so (A, B) and (B, A) are different edges.
Read A, B, C, A as a cycle because each consecutive directed edge exists and the route returns to A.
Translate the cycle back into the model, such as a possible return route in a linked website or network.

Model answer

Reveal model answer

G=(V,E),\quad V=\{Home,Products,Help\}

E=\{(Home,Products),(Products,Help),(Help,Home)\}

Home\to Products\to Help\to Home\text{ is a directed cycle}

Let V = {Home, Products, Help} and E = {(Home, Products), (Products, Help), (Help, Home)}. Home, Products, Help is a directed path because each consecutive edge exists. Home, Products, Help, Home is a directed cycle, meaning a user can return to the starting page by following links.

Practise next

Model a three-page website as a directed graph with at least one path and one cycle.
Write the vertex set and edge set for the graph.

Self-marking criteria

Defines vertices and edges in context.
Uses ordered pairs for directed edges.
Lists a valid path with each edge present.
Identifies a cycle returning to the start.
Interprets reachability in the computing model.

Extension

Change one assumption in the worked scenario and decide whether the same method still applies. If it does not, name the exact point where the reasoning breaks.

Study route

Save one clean worked answer from this lesson. Include the problem statement, notation, working, final answer and a short note explaining the computing meaning of the result.

Next lesson: Trees, Connectivity and Traversal Ideas.