Purpose and Overview

Why This Chapter Matters

Learning Objectives

1. 1Define a tree and identify its structural properties.
2. 2Distinguish between trees, forests, rooted trees, and binary trees.
3. 3Explain what a spanning tree is and why it exists in connected graphs.
4. 4Describe what makes a spanning tree a minimum spanning tree.
5. 5Apply Kruskal's algorithm to find a minimum spanning tree.
6. 6Apply Prim's algorithm to find a minimum spanning tree.
7. 7Set up and solve shortest-path problems on weighted graphs.
8. 8Trace Dijkstra's algorithm on small examples.
9. 9Identify Euler paths and circuits and state the conditions for their existence.
10. 10Identify Hamilton paths and circuits and explain why they are harder to analyze.
11. 11Describe what a planar graph is and apply Euler's formula as an introduction.
12. 12Explain how trees and network algorithms appear in computing, transportation, and data systems.
13. 13Recognize and avoid common mistakes in tree and network reasoning.

Key Terms

Sections at a Glance

• 11.1What a Tree IsDefinition of a tree; connectivity and acyclicity; the edge-count property; identifying trees, forests, and leaves
• 11.2Rooted TreesRoots, parents, children, siblings, depth, height; vocabulary of hierarchy; file systems and parse trees
• 11.3Binary Trees as an IntroductionLeft and right children; full and complete binary trees; counting leaves in full binary trees
• 11.4Spanning TreesDefinition of a spanning tree; existence in connected graphs; removing edges from cycles
• 11.5Minimum Spanning TreesWeighted graphs; the minimum spanning tree problem; why greedy algorithms succeed here
• 11.6Kruskal's AlgorithmSorting edges by weight; cycle checks; pseudocode and a full worked trace
• 11.7Prim's AlgorithmGrowing a tree from a starting vertex; pseudocode and a full worked trace; comparison with Kruskal's
• 11.8Shortest Path ProblemsSingle-source shortest paths; distance tables; the relaxation rule
• 11.9Dijkstra's Algorithm as an IntroductionNon-negative weights; pseudocode; a complete step-by-step trace
• 11.10Euler Paths and CircuitsThe Königsberg Bridge Problem; degree conditions for Euler paths and circuits
• 11.11Hamilton Paths and CircuitsVisiting every vertex once; Dirac's and Ore's theorems; the Traveling Salesman Problem
• 11.12Planar Graphs as an IntroductionDrawing without crossings; Euler's formula V − E + F = 2; K₅ and K₃,₃
• 11.13Network Optimization in Transportation and ComputingRoads, the internet, scheduling, logistics, and AI search trees
• 11.14Common Tree and Network MistakesEight recurring errors with corrections

What a Tree Is

Why These Two Conditions Together?

The Edge-Count Property

Leaves

1. State the definition of a tree in your own words. Why are both conditions — connectivity and acyclicity — necessary?
2. A graph has 9 vertices and 8 edges and is connected. Without more information, can you conclude it is a tree? Explain.
3. A graph has 9 vertices and 8 edges but is not connected. What can you conclude about this graph? Could it still be acyclic?
4. Explain why every tree with at least two vertices has at least one leaf.
5. Sketch (in words) a tree on 6 vertices that is a straight path, and a different tree on 6 vertices that is a star. How many leaves does each have?

Rooted Trees

Vocabulary of Rooted Trees

Why Rooted Trees Matter

1. A rooted tree has root R. R has children X and Y. X has children M and N. Y has child P, and P has child Q (a leaf). Identify: the leaves, the internal vertices, the depth of each vertex, and the height of the tree.
2. In a rooted tree, can the root have a sibling? Explain why or why not.
3. Two vertices in a rooted tree have the same depth. Must they be siblings? Give an example to support your answer.
4. A file system folder structure is modeled as a rooted tree. What does the root represent? What do the leaves represent?
5. Explain the difference between the depth of a vertex and the height of a tree.

Binary Trees as an Introduction

Full and Complete Binary Trees

Counting Leaves in Full Binary Trees

1. A rooted tree has a vertex with three children. Is this tree a binary tree? Explain.
2. A full binary tree has 5 internal vertices. How many leaves does it have? How many total vertices?
3. A complete binary tree has height 2. What is the maximum possible number of vertices?
4. Explain in your own words why a binary search tree is useful for storing and retrieving sorted data.
5. Draw (in words) a binary tree with 4 vertices that is not full. Identify which internal vertex has only one child.

Spanning Trees

How Many Spanning Trees Can a Graph Have?

1. A connected graph has 7 vertices and 9 edges. How many edges must be removed to form a spanning tree, and how many edges will the spanning tree have?
2. A graph has vertices P, Q, R, S with edges PQ, QR, RS, SP, and PR. Find a spanning tree by removing one edge. Which edge(s) could be removed? Are there multiple choices?
3. Explain why every connected graph has at least one spanning tree, using the cycle-removal argument from this section.
4. Can a disconnected graph have a spanning tree? Explain your reasoning.
5. A connected graph is itself a tree (it has no cycles). How many spanning trees does it have? Explain.

Minimum Spanning Trees

• The cost to lay cable between two locations.
• The distance between two cities.
• The time to transmit data between two servers.
• The construction cost of a road between two neighborhoods.

Why Greedy Algorithms Work for MSTs

1. Explain in your own words what a minimum spanning tree minimizes. What does it not minimize?
2. A weighted graph has two different spanning trees, both with total weight 20. Are both valid minimum spanning trees? Explain.
3. What does it mean for an algorithm to be "greedy"? Why is it reasonable to expect greedy choices to work for MSTs?
4. Give a real-world example (other than those listed in this section) where edge weights might represent a quantity you would want to minimize across a network.

Kruskal's Algorithm

KRUSKAL(G):
  Sort edges of G by weight (ascending)
  T = empty spanning tree (all vertices, no edges)
  For each edge e = (u, v) in sorted order:
    If u and v are in different components of T:
      Add e to T
  Return T

Why Kruskal's Algorithm Works

1. A graph has vertices P, Q, R, S, T with edges PQ (3), QR (1), RS (4), ST (2), PT (5), PR (6). Apply Kruskal's algorithm. List the edges in the order added and the total weight.
2. During Kruskal's algorithm, why is it important to check whether two vertices are already in the same component before adding an edge?
3. A graph has two edges of equal weight, both candidates at the same step of Kruskal's algorithm. Does it matter which one is chosen first? Explain.
4. Suppose Kruskal's algorithm has processed all edges but \(T\) has fewer than \(n - 1\) edges. What does this tell you about the original graph?

Prim's Algorithm

PRIM(G, s):
  T = {s}   (tree starts with only vertex s)
  While T does not include all vertices:
    Find the minimum-weight edge (u, v) where u is in T and v is not in T
    Add edge (u, v) and vertex v to T
  Return T

Kruskal's vs. Prim's

1. Apply Prim's algorithm to the graph from Practice 11.6, Problem 1 (vertices P, Q, R, S, T with edges PQ (3), QR (1), RS (4), ST (2), PT (5), PR (6)), starting from vertex P. List the vertices and edges as they are added and verify the total weight matches Kruskal's result.
2. Explain the difference between how Kruskal's algorithm and Prim's algorithm "see" the graph at each step.
3. Suppose Prim's algorithm is run from two different starting vertices on the same graph. Will the resulting minimum spanning trees necessarily contain the same edges? Will they necessarily have the same total weight?
4. Why does Prim's algorithm never need to perform a separate cycle check, unlike Kruskal's algorithm?

Shortest Path Problems

Applications

• GPS navigation: Find the fastest route from current location to destination.
• Internet routing: Find the lowest-latency path for a data packet.
• Supply chain management: Find the cheapest sequence of shipping steps.
• Flight booking: Find the route with the lowest total cost.

Setting Up a Shortest Path Problem

1. Explain the difference between "shortest path by weight" and "shortest path by edge count." Give an example of a graph where these differ.
2. A distance table currently shows \(d(v) = 12\). A new edge from a vertex \(u\) with \(d(u) = 7\) and weight 3 is examined. Apply the relaxation rule. What is the new value of \(d(v)\)?
3. Why is the distance from the source vertex to itself always 0?
4. List two real-world situations (beyond those given in this section) that can be modeled as single-source shortest path problems.

Dijkstra's Algorithm as an Introduction

DIJKSTRA(G, s):
  For each vertex v in G:
    d(v) = infinity
    visited(v) = false
  d(s) = 0

  While there are unvisited vertices:
    u = unvisited vertex with smallest d(u)
    visited(u) = true
    For each neighbor v of u where visited(v) = false:
      If d(u) + weight(u,v) < d(v):
        d(v) = d(u) + weight(u,v)

  Return d

Why Dijkstra's Algorithm Works

1. A graph has vertices A, B, C, D and edges AB (4), AC (1), BC (2), BD (5), CD (8). Apply Dijkstra's algorithm starting from A. Show the distance table after each step.
2. In the graph from problem 1, what is the shortest path (sequence of vertices) from A to D, and what is its total weight?
3. Explain in your own words why Dijkstra's algorithm "finalizes" a vertex's distance once it is marked visited.
4. Suppose a graph contains an edge with weight \(-3\). Why might Dijkstra's algorithm give an incorrect answer if applied to this graph?

Euler Paths and Circuits

The Euler Conditions

Finding an Euler Circuit or Path

1. A graph has 6 vertices, each of degree 4. Does it have an Euler circuit? Explain.
2. A graph has vertices with degrees 3, 3, 4, 4, 4. Does it have an Euler path, an Euler circuit, or neither?
3. A cycle graph \(C_6\) (a hexagon — 6 vertices arranged in a ring) has every vertex of degree 2. Does it have an Euler circuit? Describe it.
4. Explain why the sum of all vertex degrees in any graph must be even. Use this fact to explain why a graph can never have exactly one vertex of odd degree.
5. A delivery route must travel down every street in a small neighborhood exactly once and return to the depot. Under what condition on the street graph is this possible without retracing any street?

Hamilton Paths and Circuits

The Critical Difference from Euler

Sufficient Conditions

The Traveling Salesman Problem

1. A complete graph \(K_5\) has 5 vertices, each of degree 4. Does Dirac's theorem guarantee a Hamilton circuit? Verify by listing a Hamilton circuit directly.
2. A graph has 7 vertices, each with degree at least 4. Does Dirac's theorem apply? What does it conclude?
3. Explain, in your own words, why the Hamilton circuit problem is considered much harder than the Euler circuit problem.
4. A delivery driver must visit 6 locations and return to the depot. The locations form a complete weighted graph. How many distinct Hamilton circuits are there (not counting direction or starting point)? How does this number grow as the number of locations increases?
5. Can a graph have both an Euler circuit and a Hamilton circuit at the same time? Can it have one without the other? Explain with reference to the conditions for each.

Planar Graphs as an Introduction

Why Planarity Matters

• Circuit board design: Wires on a circuit board cannot cross without creating unintended connections. A circuit is planar if its connections can be laid out on one layer without crossings.
• Road maps: Roads do not typically cross without a bridge or overpass. Graphs of flat road networks are often planar.
• Geographic maps: The dual of a planar map is also a planar graph, connecting regions that share a border.

Euler's Formula for Planar Graphs

Non-Planar Graphs

• \(K_5\) (the complete graph on 5 vertices): It has 10 edges. If it were planar, Euler's formula and additional constraints would require a minimum of 10 edges — but more detailed analysis shows \(K_5\) cannot be embedded planarly.
• \(K_{3,3}\) (the complete bipartite graph on 3+3 vertices): It cannot be drawn without crossings.

1. A connected planar graph has 6 vertices and 9 edges. How many faces does it have?
2. A connected planar graph has 8 vertices and 6 faces. How many edges does it have?
3. A tree has \(n\) vertices and \(n - 1\) edges. Use Euler's formula to determine how many faces a tree has, and explain why this answer makes sense.
4. Explain why the definition of a planar graph says "can be drawn" rather than "is drawn" without crossings.
5. Why are \(K_5\) and \(K_{3,3}\) considered the fundamental obstructions to planarity?

Network Optimization in Transportation and Computing

Transportation Networks

• Shortest path algorithms like Dijkstra's find optimal routes.
• Minimum spanning trees find cheap ways to connect a new region to an existing rail network.
• Hamilton circuits approximate solutions for delivery routing (Traveling Salesman Problem).

Communication and Data Networks

Scheduling and Assignment Problems

Logistics and Distribution

• Mail and package delivery (traverse every street exactly once).
• Snow plowing and street cleaning (traverse every road without unnecessary repetition).
• Meter reading (visit every connection point exactly once).

Artificial Intelligence and Search

• Breadth-first search and depth-first search traverse trees and graphs systematically.
• A* search uses a form of Dijkstra's algorithm with a heuristic estimate of remaining distance.
• Game trees represent possible future states in games like chess or Go, branching from each decision point.
• Decision trees in machine learning branch at each feature to classify data points.

1. Explain how a minimum spanning tree could help a company decide where to install new fiber-optic lines.
2. Why might a switched network use a spanning tree rather than allowing all possible connections to remain active?
3. Describe, in your own words, the difference between the Euler circuit problem and the Chinese Postman Problem.
4. Explain how a game tree models the possible moves in a game like tic-tac-toe.

Common Tree and Network Mistakes

Chapter Summary

• Sec 11.1A tree is a connected graph with no cycles. A tree on n vertices has exactly n − 1 edges, and every pair of vertices is connected by exactly one simple path. A forest is an acyclic graph that may be disconnected.
• Sec 11.2A rooted tree designates one vertex as the root, introducing the hierarchy of parent, child, sibling, depth, and height. Rooted trees underlie file systems, parse trees, decision trees, and binary search trees.
• Sec 11.3A binary tree is a rooted tree where every vertex has at most two children. Full binary trees have every internal vertex with exactly two children; the number of leaves equals the number of internal vertices plus one.
• Sec 11.4A spanning tree of a connected graph includes all vertices and forms a tree. Every connected graph has at least one spanning tree, found by removing edges from cycles until none remain.
• Sec 11.5A minimum spanning tree (MST) of a weighted graph has the smallest possible total edge weight among all spanning trees. Greedy algorithms succeed for MSTs because of the cut property.
• Sec 11.6Kruskal's algorithm sorts all edges by weight and greedily adds each edge that does not create a cycle, stopping after n − 1 edges. It works globally across the whole edge list.
• Sec 11.7Prim's algorithm grows a tree from a single starting vertex, always adding the cheapest edge connecting the tree to a new vertex. It works locally, expanding outward.
• Sec 11.8The shortest path problem asks for the minimum-weight path between vertices. The relaxation rule updates a distance estimate when a shorter route through a known vertex is discovered.
• Sec 11.9Dijkstra's algorithm solves the single-source shortest path problem for graphs with non-negative edge weights, repeatedly finalizing the closest unvisited vertex and relaxing its neighbors.
• Sec 11.10Euler paths and circuits traverse every edge exactly once. A connected graph has an Euler circuit if and only if all degrees are even, and an Euler path if and only if exactly two vertices have odd degree.
• Sec 11.11Hamilton paths and circuits visit every vertex exactly once. No simple characterization exists; the Hamilton circuit problem is NP-complete. Dirac's and Ore's theorems give sufficient (not necessary) conditions.
• Sec 11.12A planar graph can be drawn without edge crossings. Euler's formula V − E + F = 2 relates vertices, edges, and faces for connected planar graphs. K₅ and K₃,₃ are the fundamental non-planar graphs.
• Sec 11.13Network optimization applies trees and network algorithms to transportation, communication, scheduling, logistics, and AI search — connecting discrete mathematics directly to real systems.
• Sec 11.14Eight recurring mistakes involve confusing trees with general graphs, assuming unique spanning trees, misapplying Dijkstra's algorithm, conflating Euler and Hamilton problems, forgetting the outer face, and confusing MSTs with shortest paths.

Key Terms Review

Concept Review Questions

Answer in full sentences.

1. State the definition of a tree. What two conditions must both be satisfied?
2. What is the relationship between the number of vertices and the number of edges in a tree?
3. What is the difference between a tree and a forest?
4. What does it mean for a tree to be rooted? What vocabulary does the root introduce?
5. What is a binary tree? Give an example of where binary trees appear in computing.
6. What is a spanning tree of a connected graph? How is it different from the original graph?
7. What makes a spanning tree a minimum spanning tree?
8. State the main idea behind Kruskal's algorithm in one or two sentences.
9. State the main idea behind Prim's algorithm in one or two sentences.
10. What does Dijkstra's algorithm compute? What restriction does it require on edge weights?
11. What is the relaxation step in Dijkstra's algorithm? Why is it necessary?
12. State the condition for an Euler circuit to exist in a connected graph.
13. State the condition for an Euler path (not a circuit) to exist in a connected graph.
14. What is the difference between an Euler path and a Hamilton path?
15. Why is the Hamilton circuit problem considered harder than the Euler circuit problem?
16. Define a planar graph. Does a graph's planarity depend on how it is drawn?
17. State Euler's formula for connected planar graphs. What do V, E, and F represent?
18. What are \(K_5\) and \(K_{3,3}\)? Why are they significant?

Tree Practice

1. Determine whether each graph is a tree, a forest, or neither: (a) 6 vertices, 5 edges, connected, no cycles. (b) 6 vertices, 5 edges, two components. (c) 6 vertices, 6 edges, connected. (d) 1 vertex, 0 edges.
2. A tree has 9 vertices. How many edges does it have?
3. Can a tree have a cycle? Explain.
4. A tree has 12 edges. How many vertices does it have?

1. Draw a rooted tree with root A, where A has children B and C, B has children D and E, and C has child F (a leaf). F has child G. (a) What is the height of the tree? (b) What is the depth of G? (c) What are the leaves? (d) Who is the parent of E?
2. A rooted binary tree has 7 vertices. What is the minimum possible height? What is the maximum possible height?
3. Explain why a rooted tree with height 3 can have at most \(2^4 - 1 = 15\) vertices if it is a binary tree.

1. List all non-isomorphic trees with exactly 4 vertices. (Isomorphic trees have the same structure up to labeling.)
2. A tree is called a path if it looks like a sequence of vertices with each connected to the next. A tree is called a star if one central vertex is connected to all others. Describe the degree sequence of: (a) a path on 5 vertices. (b) a star with 5 vertices (one center, four leaves).
3. A tree on 8 vertices has exactly one vertex of degree 4. What are the possible degree sequences for such a tree? (Remember: the sum of all degrees equals twice the number of edges.)

Answers may be placed in the answer key.

Spanning Tree Practice

1. Does every connected graph have a spanning tree? Does every disconnected graph have a spanning tree?
2. How many edges does a spanning tree of a connected graph on 10 vertices have?
3. If a connected graph on 7 vertices has 10 edges, how many edges must be removed to produce a spanning tree?

1. A graph has vertices A, B, C, D, E and edges AB, AC, BC, BD, CD, CE, DE. Find two different spanning trees of this graph. Confirm each has the correct number of edges.
2. A graph has vertices A, B, C, D, E, F with edges and weights: AB: 3, AC: 1, BC: 4, BD: 2, CD: 5, CE: 6, DE: 7, EF: 2, DF: 9. Apply Kruskal's algorithm to find a minimum spanning tree. List the edges in the order they are added and the total weight.
3. Apply Prim's algorithm to the same graph in problem 2, starting from vertex A. List the vertices and edges as they are added and verify the total weight matches.
4. Two students apply Kruskal's algorithm to a graph. One student gets the spanning tree {AC, BD, AB, CE, EF}. The other gets {AC, BD, BC, CE, EF}. Both have total weight 14. Can both be correct? Explain.

Answers may be placed in the answer key.

Shortest Path Practice

1. What is the difference between a shortest path and a minimum spanning tree?
2. Can a shortest path between two vertices include a vertex more than once? Why or why not?
3. Why does Dijkstra's algorithm require non-negative edge weights?

1. A weighted graph has vertices A, B, C, D, E and edges: AB: 10, AC: 3, BC: 4, BD: 8, CD: 6, CE: 7, DE: 2. Apply Dijkstra's algorithm starting from A. Show the distance table after each step. What is the shortest distance from A to D?
2. In the graph from problem 1, trace the actual shortest path (not just the distance) from A to D. What sequence of vertices does it use?
3. A student applies Dijkstra's algorithm and selects vertex C before vertex B, even though d(B) < d(C) at the time. What mistake has the student made? How would this affect the result?
4. A weighted graph has edges AB: 5, AC: 2, BC: 1, BD: 4, CD: 3. Starting from A, find the shortest distances to all other vertices. Which path connects A to D most cheaply?

Answers may be placed in the answer key.

Euler and Hamilton Practice

1. For each graph described, determine whether an Euler circuit, Euler path (not circuit), or neither exists. (a) All 6 vertices have degree 4. (b) Exactly 2 vertices have odd degree; the rest are even. (c) All 5 vertices have odd degree. (d) A cycle graph \(C_6\) (a hexagon — 6 vertices arranged in a ring).
2. A graph has 8 vertices with degrees 2, 2, 3, 3, 4, 4, 5, 5. Does it have an Euler circuit? An Euler path?
3. A graph has 5 vertices with degrees all equal to 2. What type of graph is this? Does it have an Euler circuit?
4. Explain why the sum of all degrees in any graph must be even. Use this to explain why a graph can never have exactly one vertex of odd degree.

1. A complete graph \(K_4\) has 4 vertices, each with degree 3. Does Dirac's theorem guarantee a Hamilton circuit? Check directly whether a Hamilton circuit exists by listing the vertices.
2. A graph has 8 vertices. Each vertex has degree at least 4. Does Dirac's theorem apply? What does it conclude?
3. A graph has 6 vertices with degrees 2, 2, 3, 3, 3, 3. Does Dirac's theorem guarantee a Hamilton circuit?
4. Explain in your own words why the Hamilton circuit problem is considered much harder than the Euler circuit problem.
5. A delivery driver must visit 5 locations and return to the starting depot. The locations form a complete weighted graph (all pairwise distances given). How many distinct Hamilton circuits are there (not counting direction or starting point)? How does this number grow as the number of locations increases?

Answers may be placed in the answer key.

Applications

1. Apply Kruskal's algorithm to find the minimum spanning tree. What routes should be built, and what is the total cost?
2. If the route Hub to C (cost 3) is unavailable (the terrain makes it infeasible), apply Kruskal's algorithm again. How does the MST change? What is the new total cost?

1. Apply Dijkstra's algorithm from Central. What is the minimum travel time from Central to Terminal?
2. What sequence of stations minimizes travel from Central to Terminal?
3. If the East–Terminal connection closes, what is the new minimum travel time from Central to Terminal?

1. Count the degree of each intersection.
2. Does an Euler circuit exist? If not, how many odd-degree vertices are there?
3. If the department must traverse every street at least once and wants to minimize repetitions, which streets must be repeated, and why?

1. Model this as a graph. Is it planar? (Draw it and try to arrange components so no connections cross.)
2. If the board has 5 components (vertices) and 7 connections (edges) and is planar, how many faces does Euler's formula predict?
3. Explain why minimizing connections (using a spanning tree) might reduce the risk of short circuits.

Error Analysis

In each problem below, a student has made an error. Identify the error and explain the correct approach.

Answers may be placed in the answer key.

Chapter 11 Checkpoint