Graph Theory and Trees

Introduction

Graph theory provides a mathematical language for representing relationships, connections, movement, and dependency. In a computer application, a graph may represent a social network, a computer network, links between web pages, roads between cities, dependencies among software modules, or transitions between states of a program. Trees are a particularly important class of graphs used in file systems, database indexes, compilers, communication networks, and artificial intelligence.

A graph consists of objects called vertices and relationships called edges. The power of graph theory lies in its ability to model structure independently of the physical form of a problem. Once a problem is represented as a graph, established algorithms can be used to search, optimize, schedule, classify, and analyze it.

Learning Objectives

After studying this chapter, you should be able to:

• define graphs, directed graphs, weighted graphs, and trees;
• represent graphs using adjacency matrices, adjacency lists, and incidence matrices;
• analyze degree, paths, cycles, connectivity, and components;
• distinguish Euler and Hamilton structures;
• apply graph-coloring and planarity concepts;
• construct and analyze spanning trees and minimum spanning trees;
• use breadth-first search, depth-first search, and shortest-path algorithms;
• explain the basic idea of network flow;
• select suitable graph models for routing, scheduling, social networks, and dependency analysis.

1. Fundamental Graph Concepts

A graph is written as G = (V,E), where V is a nonempty set of vertices and E is a set of edges joining pairs of vertices. In an undirected graph, an edge joining vertices u and v is written {u,v}; the order does not matter. In a directed graph, or digraph, an edge is an ordered pair (u,v), representing an arc from u to v.

A graph may have parallel edges, meaning multiple edges connecting the same pair of vertices, and loops, meaning an edge from a vertex to itself. A simple graph has neither loops nor parallel edges. Unless stated otherwise, the term graph in this chapter means a finite simple graph.

Important terms include:

• Adjacent vertices: vertices joined by an edge.
• Incident edge: an edge connected to a vertex.
• Order: the number of vertices, |V|.
• Size: the number of edges, |E|.
• Neighborhood: the set of vertices adjacent to a specified vertex.
• Degree: the number of edges incident with a vertex. In a simple undirected graph it is written deg(v).
• Isolated vertex: a vertex of degree zero.
• Pendant or leaf vertex: a vertex of degree one.

For every finite undirected graph,

This is the handshaking lemma. Each edge contributes two to the total degree: one at each endpoint. Consequently, the number of odd-degree vertices is always even.

In a directed graph, the indegree deg^-(v) counts arcs entering a vertex and the outdegree deg^+(v) counts arcs leaving it. Therefore,

These identities assume that each edge or arc is counted once and that loops are treated according to the stated graph convention.

A weighted graph assigns a numerical weight to each edge. Weights may represent distance, cost, time, bandwidth, risk, or capacity. A weight need not always be positive, although several shortest-path algorithms require nonnegative weights.

2. Graph Representations

The same graph can be stored in different ways. The best representation depends on the graph’s density and the operations required.

Adjacency Matrix

For a graph with n vertices, an adjacency matrix is an n × n matrix A, where

For a simple undirected graph, A is symmetric and its diagonal entries are zero. For a weighted graph, A[i,j] may contain the edge weight, while a special value such as infinity denotes no edge. An adjacency matrix uses O(n²) storage and tests adjacency in constant time, O(1). It is suitable for dense graphs.

Adjacency List

An adjacency list stores, for each vertex, a list of its neighbors. It uses O(|V| + |E|) storage and is efficient for sparse graphs. Traversal algorithms such as breadth-first search and depth-first search commonly use this representation.

Incidence Matrix

An incidence matrix has one row per vertex and one column per edge. In an undirected graph, an entry is 1 when the vertex is an endpoint of the edge and 0 otherwise. In a directed graph, a common convention uses −1 at the tail and +1 at the head. Incidence matrices are useful in network optimization and algebraic graph analysis.

Choosing a Representation

3. Walks, Trails, Paths, and Cycles

A walk is a sequence of vertices and edges in which consecutive vertices are connected. Vertices and edges may repeat. A trail is a walk with no repeated edge. A path is a walk with no repeated vertex. A closed walk begins and ends at the same vertex. A cycle is a closed path whose starting vertex is the only repeated vertex.

The length of a walk is the number of edges it contains. In a weighted graph, its total weight is the sum of the weights of its edges:

Here, P is a path and w(e) is the weight of edge e. This formula is applicable when path cost is additive.

In a directed graph, a path must follow the direction of every arc. A graph is connected if every pair of distinct vertices is joined by a path. A directed graph is strongly connected if every vertex can reach every other vertex following directions. It is weakly connected if it becomes connected when arc directions are ignored.

A connected component is a maximal connected subgraph. If a graph has several components, no path connects vertices belonging to different components.

4. Euler and Hamilton Structures

An Euler trail uses every edge exactly once. An Euler circuit is an Euler trail that starts and ends at the same vertex. For a connected undirected graph:

• an Euler circuit exists if and only if every vertex has even degree;
• an Euler trail but no Euler circuit exists if and only if exactly two vertices have odd degree.

Vertices of degree zero may be ignored when assessing connectivity, provided all non-isolated vertices lie in one connected component.

A Hamilton path visits every vertex exactly once. A Hamilton cycle visits every vertex exactly once and returns to its starting vertex. Unlike Euler conditions, there is no simple degree-based necessary-and-sufficient test for Hamiltonicity in general graphs. Determining whether a general graph has a Hamilton cycle is computationally difficult, which is why practical methods often use heuristics or exploit special graph structures.

Euler problems concern edges; Hamilton problems concern vertices. This distinction is central in route inspection, delivery planning, circuit design, and itinerary construction.

5. Graph Coloring

A proper vertex coloring assigns colors to vertices so that adjacent vertices receive different colors. The smallest number of colors required is the chromatic number, written χ(G). A graph with χ(G) = k is called k-chromatic.

A graph is bipartite if its vertices can be divided into two disjoint sets so that every edge joins vertices in different sets. A graph is bipartite if and only if it contains no odd cycle. Thus, a two-coloring test can also determine whether a graph is bipartite.

Coloring applications include:

• assigning examination times so that students taking two conflicting courses are not scheduled simultaneously;
• assigning radio frequencies to nearby transmitters;
• allocating registers in a compiler;
• assigning machines or rooms to mutually conflicting activities.

A greedy coloring algorithm processes vertices in an order and assigns each vertex the smallest color not used by its already-colored neighbors. Greedy coloring is fast, but the result can depend strongly on vertex order and may use more colors than necessary.

6. Planar Graphs

A graph is planar if it can be drawn in the plane so that edges intersect only at common endpoints. A particular crossing-free drawing is a planar embedding. Planarity is important in printed circuit layouts, geographic maps, and visual network design.

For a connected planar graph with v vertices, e edges, and f faces, Euler’s formula is

The outer unbounded region counts as a face. For a simple connected planar graph with v ≥ 3,

This bound provides a useful test: a simple graph exceeding it cannot be planar. The complete graph K₅ and the complete bipartite graph K_3,3 are standard nonplanar graphs. A graph may be nonplanar even when a particular drawing happens to contain crossings; alternatively, crossings may sometimes be removed by rearranging the drawing.

7. Trees and Their Properties

A tree is a connected undirected graph with no cycles. Equivalent characterizations for a finite graph are:

1. it is connected and acyclic;
2. there is exactly one path between every pair of vertices;
3. it is connected and has n−1 edges when it has n vertices;
4. adding any new edge creates exactly one cycle;
5. removing any edge disconnects it.

A forest is an acyclic graph that may be disconnected. Its components are trees. In a rooted tree, one vertex is selected as the root. The terms parent, child, ancestor, descendant, level, height, and subtree describe relationships relative to that root.

A binary tree is a rooted tree in which each node has at most two children. In a binary search tree, keys in the left subtree are smaller than the node’s key and keys in the right subtree are larger, under the chosen ordering rule. Search, insertion, and deletion have average performance related to tree height; an unbalanced tree may degrade toward linear time, while balanced trees maintain logarithmic height.

A spanning tree of a connected graph is a subgraph containing every vertex and forming a tree. A graph can have many spanning trees. If a graph is disconnected, a spanning forest can be formed instead.

8. Traversal Algorithms

Breadth-First Search

Breadth-first search (BFS) explores vertices in layers according to their distance in edges from a starting vertex. It uses a queue. In an unweighted graph, BFS finds a shortest path in terms of number of edges.

A typical BFS procedure marks a start vertex, places it in a queue, repeatedly removes the front vertex, and adds each unvisited neighbor to the rear. With adjacency lists, its time complexity is O(|V|+|E|), because each vertex and edge is processed a bounded number of times.

Depth-First Search

Depth-first search (DFS) explores as far as possible along one branch before backtracking. It can be implemented recursively or with a stack. DFS supports connected-component detection, cycle detection, topological sorting, and articulation-point analysis. With adjacency lists its time complexity is also O(|V|+|E|).

For a directed acyclic graph, a topological ordering is a linear ordering of vertices such that every directed edge goes from an earlier to a later vertex. It exists if and only if the graph has no directed cycle. Topological ordering is useful for course prerequisites, build systems, and task dependencies.

9. Shortest Paths

The shortest-path problem seeks a path of minimum total weight between specified vertices. The appropriate algorithm depends on edge properties.

• Unweighted graph: BFS gives minimum edge-count distance.
• Nonnegative edge weights: Dijkstra’s algorithm is appropriate.
• Negative edges but no reachable negative cycle: Bellman–Ford can be used.
• All-pairs shortest paths: Floyd–Warshall is a dynamic-programming method, usually with time complexity O(|V|³).

Dijkstra’s algorithm maintains a tentative distance d(v) for each vertex. Initially, d(s)=0 for source s and all other distances are infinity. Repeatedly, it selects the unprocessed vertex with smallest tentative distance and relaxes each outgoing edge. Relaxation tests whether

If so, it replaces d(v) by d(u)+w(u,v). Dijkstra’s correctness requires all edge weights to be nonnegative. If negative edges are present, a vertex finalized too early may later receive a lower distance.

10. Minimum Spanning Trees

For a connected weighted undirected graph, a minimum spanning tree (MST) is a spanning tree with minimum total edge weight. If the selected edges are T, its weight is

An MST contains exactly n−1 edges for n vertices. It need not provide the shortest path between every pair of vertices; it minimizes total network connection cost, not individual route distance.

Kruskal’s algorithm sorts edges by nondecreasing weight and repeatedly adds the next edge if it does not create a cycle. A disjoint-set data structure efficiently detects whether two endpoints already belong to the same component.

Prim’s algorithm starts with one vertex and repeatedly adds the cheapest edge connecting the current tree to a vertex outside it. Both algorithms are greedy and are correct because of the cut and cycle properties of spanning trees. If all edge weights are distinct, the MST is unique; with equal weights, multiple MSTs may exist.

11. Network Flows

A flow network is a directed graph with a source s, a sink t, and nonnegative capacity c(u,v) on each arc. A flow f(u,v) must satisfy:

For every intermediate vertex, flow conservation requires total inflow to equal total outflow:

The value of a flow is the net flow leaving the source, equivalently the net flow entering the sink. The maximum-flow problem seeks the largest feasible flow. The max-flow min-cut theorem states that the maximum flow value equals the capacity of a minimum cut separating source from sink.

Applications include data transmission, transportation, water distribution, job assignment, and supply-chain capacity planning. Capacities may represent physical limits, contractual limits, or processing rates.

12. Worked Example: A Campus Network

Consider a campus with buildings A, B, C, D, and E. Undirected links have the following installation costs:

To construct an MST using Kruskal’s algorithm, sort the edges:

B–C (1), A–C (2), D–E (2), A–B (4), B–D (5), B–E (7), C–D (8), C–E (10).

Select B–C, A–C, and D–E. The next edge A–B would form a cycle A–C–B–A, so reject it. Select B–D, which joins the two current components. Four edges have now been selected for five vertices, so the result is a spanning tree:

T = {B–C, A–C, D–E, B–D}

Its total cost is

The network is connected at minimum total installation cost according to the given edge weights. However, the cheapest route from A to E in this tree is A–C–B–D–E, with cost 2+1+5+2=10. A different graph path might be shorter if an additional link were installed. This illustrates the difference between minimizing total infrastructure cost and minimizing every individual route.

13. Applied Case: Prerequisite and Project Scheduling

Background. A software company is developing a mobile application. Activities have dependencies: requirements must precede design, design must precede implementation, implementation must precede testing, and testing must precede deployment. Documentation may begin after requirements and proceed independently.

Problem. The project manager needs to determine whether the dependency plan is feasible and identify an execution order.

Analysis. Model activities as vertices and prerequisites as directed edges. For example, Requirements → Design → Implementation → Testing → Deployment, with Requirements → Documentation. The graph is a directed acyclic graph if no activity eventually depends on itself.

Approach. Apply DFS cycle detection or repeatedly remove vertices of indegree zero. A valid topological order is Requirements, Design, Documentation, Implementation, Testing, Deployment. Documentation could also occur later, provided its prerequisite is complete.

Outcome. The ordering identifies tasks that can begin immediately and tasks that must wait. If an edge Deployment → Design were accidentally added, a directed cycle would result, proving that the dependency specification is inconsistent.

Learning points. Graph models expose hidden dependencies, support parallel execution, and provide a basis for build tools and project-management systems. A topological order is not necessarily a schedule with dates; durations, resources, and capacity constraints require additional scheduling analysis.

14. Professional Applications and Limitations

Graph methods support routing protocols, GPS navigation, recommendation systems, fraud detection, social-network analysis, compiler optimization, database query planning, and cloud-service dependency mapping. In social networks, vertices may represent users and edges relationships; directed and weighted edges can model follows, interaction frequency, or trust.

Practical limitations must be recognized. Large graphs may exceed memory limits, dynamic networks change over time, and data may be incomplete or biased. A graph representation can also oversimplify relationships: a single edge may hide time, direction, context, or uncertainty. Algorithmic outputs are only as reliable as the graph and weights supplied.

Ethically, network analysis can expose personal relationships, infer sensitive attributes, or enable surveillance. Systems should apply data minimization, access controls, anonymization where appropriate, documented retention policies, and fairness testing. When graph algorithms influence employment, credit, policing, or education, organizations should provide governance, auditability, and human review. AI-based graph learning may identify patterns in large networks, but it does not remove the need to validate data quality, explain decisions, and monitor discriminatory effects.

Best practices include clearly defining vertices and edges, documenting direction and weight meanings, checking connectivity and data quality, selecting algorithms according to graph properties, analyzing worst-case complexity, testing on representative cases, and distinguishing infrastructure optimization from route optimization.

Chapter Summary

Graph theory models entities and relationships using vertices and edges. Graphs may be undirected, directed, weighted, simple, connected, or planar. Adjacency matrices provide fast edge lookup, while adjacency lists are storage-efficient for sparse networks. Degree, paths, cycles, connectivity, Euler structures, Hamilton structures, coloring, and planarity describe important graph properties.

Trees are connected acyclic graphs with exactly one path between every pair of vertices and n−1 edges for n vertices. BFS and DFS provide fundamental traversal methods. BFS finds shortest paths in unweighted graphs, while Dijkstra’s algorithm handles nonnegative weighted edges. Kruskal’s and Prim’s algorithms construct minimum spanning trees, and flow models analyze capacity-constrained movement. These tools support routing, scheduling, dependencies, network design, and social-network analysis, but their conclusions depend on appropriate modeling, reliable data, computational feasibility, and ethical governance.

Key Terms

Graph: A structure consisting of vertices and edges.

Vertex: An object or entity represented in a graph.

Edge: A connection between two vertices.

Directed graph: A graph whose edges have direction.

Weighted graph: A graph whose edges carry numerical values.

Degree: The number of edges incident with a vertex.

Path: A walk with no repeated vertex.

Cycle: A closed path with no repeated vertex except its start and end.

Connected graph: A graph in which every pair of vertices has a path between them.

Euler circuit: A closed trail using every edge exactly once.

Hamilton cycle: A cycle visiting every vertex exactly once.

Chromatic number: The minimum number of colors required for a proper vertex coloring.

Planar graph: A graph drawable without edge crossings except at endpoints.

Tree: A connected acyclic undirected graph.

Rooted tree: A tree with one distinguished vertex called the root.

Spanning tree: A tree containing every vertex of a connected graph.

Breadth-first search: A layer-by-layer graph traversal using a queue.

Depth-first search: A branch-oriented traversal using recursion or a stack.

Topological ordering: An ordering of a directed acyclic graph respecting all edge directions.

Minimum spanning tree: A spanning tree of minimum total edge weight.

Review Questions

Short Answer Questions

1. State the handshaking lemma for a finite undirected graph.
2. What is the difference between an Euler circuit and a Hamilton cycle?
3. Give two advantages of an adjacency list.
4. Define a spanning tree.
5. Why can Dijkstra’s algorithm fail when negative edge weights are present?

Long Answer Questions

1. Explain adjacency matrices, adjacency lists, and incidence matrices, including their storage requirements and suitable applications.
2. Describe the conditions for Euler trails and Euler circuits in connected undirected graphs, and contrast them with Hamilton paths and cycles.
3. Prove or explain three equivalent characterizations of a finite tree.
4. Compare BFS and DFS in terms of data structures, applications, and time complexity.
5. Explain Kruskal’s and Prim’s algorithms and discuss why an MST does not necessarily provide shortest routes between all vertex pairs.

Analytical / Application Questions

1. A communication network has six sites and weighted links. Design an algorithmic strategy to connect all sites at minimum installation cost, and explain how you would verify that the result is a spanning tree.
2. A university timetable contains conflicts between courses. Formulate the problem as a graph-coloring problem and explain what vertices, edges, and colors represent.
3. A project dependency graph contains the edges Requirements → Design, Design → Coding, Coding → Testing, Testing → Deployment, and Deployment → Design. Determine whether a valid topological ordering exists and justify your answer.

Multiple Choice Questions with Answers

Question 1

For a finite undirected graph, the sum of all vertex degrees equals:

A. |E|

B. 2|E|

C. |V| + |E|

D. |V|²

Correct Answer: B. 2|E|

Question 2

Which representation is generally most storage-efficient for a sparse graph?

A. Adjacency matrix

B. Adjacency list

C. Distance matrix

D. Identity matrix

Correct Answer: B. Adjacency list

Question 3

A connected undirected graph has an Euler circuit exactly when:

A. Every vertex has odd degree

B. Exactly two vertices have odd degree

C. Every vertex has even degree

D. It has no cycles

Correct Answer: C. Every vertex has even degree

Question 4

A finite tree with 12 vertices has how many edges?

A. 10

B. 11

C. 12

D. 13

Correct Answer: B. 11

Question 5

Which algorithm finds shortest paths in an unweighted graph from a chosen source?

A. Breadth-first search

B. Kruskal’s algorithm

C. Prim’s algorithm

D. Floyd’s cycle algorithm

Correct Answer: A. Breadth-first search

Question 6

Dijkstra’s algorithm requires edge weights to be:

A. All equal to one

B. Nonnegative

C. All negative

D. Prime numbers

Correct Answer: B. Nonnegative

Question 7

A graph is bipartite if and only if it contains no:

A. Path

B. Even cycle

C. Odd cycle

D. Leaf vertex

Correct Answer: C. Odd cycle

Question 8

In a topological ordering, every directed edge must point:

A. From a later vertex to an earlier vertex

B. Between vertices of equal degree

C. From an earlier vertex to a later vertex

D. Only toward the root

Correct Answer: C. From an earlier vertex to a later vertex

Question 9

What is the main objective of a minimum spanning tree?

A. Minimize the longest individual path

B. Minimize total edge weight while connecting all vertices

C. Visit every edge exactly once

D. Maximize the number of cycles

Correct Answer: B. Minimize total edge weight while connecting all vertices

Question 10

In a flow network, flow conservation at an intermediate vertex requires:

A. Inflow equals outflow

B. Capacity equals zero

C. Every incident edge has equal capacity

D. The vertex has indegree zero

Correct Answer: A. Inflow equals outflow