Fundamentals of Computing: Trees, Connectivity and Traversal Ideas

Lesson overview

Reason about connected graph structures used in computing.

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

Identify connected components.
Distinguish trees from general graphs.
Trace a simple breadth-first or depth-first traversal.

Learning outcomes

By the end of this lesson, you can identify connected components.
By the end of this lesson, you can distinguish trees from general graphs.
By the end of this lesson, you can trace a simple breadth-first or depth-first traversal.

Key vocabulary

What this lesson is about

Unless stated otherwise, this lesson uses the common finite undirected graph definition: a tree is connected and acyclic. The edge-count rule |E| = |V| − 1 is useful, but by itself it does not prove a graph is a tree.

Connectivity asks whether vertices are reachable from one another. Traversal is the process of visiting vertices in a systematic order, and that order depends on the start vertex and adjacency order.

These ideas are fundamental to file systems, search, parsing, routing and hierarchical data. The title combines structure and algorithmic movement through that structure.

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.

TreeGraph structure. A connected graph with no cycles.

TraversalAlgorithmic idea. A systematic process for visiting vertices in a graph or tree.

BFS (Breadth-first search)Acronym. A traversal algorithm that explores all neighbours at the current distance before moving further away.

DFS (Depth-first search)Acronym. A traversal algorithm that follows one branch as far as possible before backtracking.

Formal notation and definitions

A tree is a connected acyclic graph. For a finite tree, |E| = |V| - 1. Traversal order is an algorithmic choice, not a property of the graph alone.

How to read the symbols

$|E|=|V|-1$ For a finite tree, the number of edges is one less than the number of vertices.

connectedEvery vertex is reachable from every other vertex.

acyclicContains no cycles.

Use the tree definition to check both connectedness and absence of cycles. Traversal describes an algorithm over the structure.

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

A folder hierarchy is tree-like when each item has one parent, while a website can contain cycles because pages link back to earlier pages.

Objects: vertices, edges, finite undirected tree conditions, the root or starting vertex, parent-child links, and the traversal order.

Model cue: Use a rooted tree and mark parent-child relationships. Then compare it with a graph that has an extra edge forming a cycle.

2. Mathematical working

|V|=5,\quad |E|=4

\text{connected}+\text{acyclic}\Rightarrow\text{tree}

\text{BFS order from }r:\quad r,a,b,c,d\quad\text{for one chosen adjacency order}

\text{For finite undirected graphs, }|E|=|V|-1\text{ alone is not enough without connectedness or acyclicity}

Plain text version

A tree is a connected acyclic graph.
For a finite tree, |E| = |V| − 1.
Traversal order is an algorithmic choice, not a property of the graph alone.

Worked use: For finite undirected graphs, a tree is connected and acyclic. A folder hierarchy is tree-like because each folder has one parent, except the root. Adding shortcuts can create cycles or multiple paths, so the tree assumption must be checked. The count |E| = |V| - 1 is necessary for a finite tree, but it is not enough unless connectedness or acyclicity is also established.

3. How to read the working

Use |V| and |E| to check a necessary tree condition for finite graphs: a tree with five vertices has four edges.
Do not use the edge count alone. The graph must also be connected and acyclic.
Read the BFS order as algorithm-dependent: it depends on the chosen start vertex and adjacency order.
Use the finite undirected assumption unless a question states a different tree definition.
Translate traversal order into computing behaviour, such as the order in which folders, pages or states are visited.

4. Computing meaning and check

The tree conditions protect algorithmic assumptions. Traversal results are meaningful only when the structure being traversed has been correctly identified.

Now check: Explain why a connected graph with |V| vertices and |V| edges cannot be a tree. Then give a disconnected graph with |E| = |V| - 1 to show why edge count alone is not enough.

Worked example

From scenario to formal reasoning

Scenario: A folder hierarchy is tree-like when each item has one parent, while a website can contain cycles because pages link back to earlier pages.

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

Reveal model answer

For finite undirected graphs, a tree is connected and acyclic. A folder hierarchy is tree-like because each folder has one parent, except the root. Adding shortcuts can create cycles or multiple paths, so the tree assumption must be checked. The count |E| = |V| - 1 is necessary for a finite tree, but it is not enough unless connectedness or acyclicity is also established.

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 tree is a connected acyclic graph.
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 calling every connected diagram a tree. A tree is connected and acyclic.

Guided practice

Check whether a finite undirected graph with |V| = 5 and |E| = 4 is necessarily a tree.
Give a connected acyclic example and a disconnected acyclic counterexample.
Trace BFS and DFS from the same root using a stated adjacency order.
Explain why traversal order is algorithm-dependent rather than a graph property alone.

Quick checks

1. For finite undirected graphs, edge count alone is:

irrelevant to treesnot enough to prove a graph is a treealways enough to prove a graph is a tree

2. BFS traversal order depends on:

only the number of verticesonly whether the graph is drawn neatlystart vertex and adjacency order

Digital exam practice

Example exam task

For the finite undirected graph V = {r,a,b,c,d}, E = {{r,a},{r,b},{a,c},{a,d}}, decide whether it is a tree using connectedness, acyclicity and |E| = |V| - 1. Then trace BFS from r using adjacency order a before b and c before d.

Notation toolkit

|E|=|V|-1

Means: a necessary edge count for finite trees

How to use: Use it as a check, not as the only proof.

\operatorname{connected}(G)

Means: every vertex can be reached from every other vertex

How to use: Use it when distinguishing trees from disconnected graphs.

BFS_r

Means: breadth-first traversal from root r

How to use: Use it when the start vertex and adjacency order are stated.

What a good answer is expected to show

A strong answer for this lesson defines vertices, edges, finite undirected tree conditions, the root or starting vertex, parent-child links, and the traversal order, applies the graph theory method with visible working, and finishes by interpreting the result in the computing scenario.

How to solve it

Use |V| and |E| to check a necessary tree condition for finite graphs: a tree with five vertices has four edges.
Do not use the edge count alone. The graph must also be connected and acyclic.
Read the BFS order as algorithm-dependent: it depends on the chosen start vertex and adjacency order.
Use the finite undirected assumption unless a question states a different tree definition.
Translate traversal order into computing behaviour, such as the order in which folders, pages or states are visited.

Model answer

Reveal model answer

|V|=5,\quad |E|=4=|V|-1

\operatorname{connected}(G)\land\operatorname{acyclic}(G)\Rightarrow G\text{ is a tree}

BFS_r:\ r,a,b,c,d

For V = {r,a,b,c,d} and E = {{r,a},{r,b},{a,c},{a,d}}, the graph is finite, undirected, connected and has no cycle, so it is a tree; also |E| = 4 = |V| - 1. With adjacency order a before b and c before d, BFS from r visits r, a, b, c, d. Traversal order depends on the start and adjacency order.

Practise next

Check whether a finite undirected graph with |V| = 5 and |E| = 4 is necessarily a tree.
Give a connected acyclic example and a disconnected acyclic counterexample.

Self-marking criteria

States the finite undirected assumption.
Checks connectedness and acyclicity, not only edge count.
Uses |E| = |V| - 1 as a necessary tree check.
States start vertex and adjacency order for traversal.
Explains traversal order as algorithm-dependent.

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: Graph Models for Networks, Dependencies and Systems.