MGU Mathematics Series — Combinatorics
Part V: Graphs, Designs, and Capstone Applications
Vertices · Edges · Trees · Coloring · Network Counting
Chapter 12 of 14
MGU Mathematics Series  ·  Combinatorics  ·  Library Textbook Edition

Chapter 12:
Graph Counting and
Network Structures

Vertices, edges, degrees, the Handshaking Lemma, complete graphs, bipartite graphs, paths, cycles, trees, spanning trees, coloring, and counting network configurations — combinatorics in the language of finite relationships

■ Math Level: Combinatorics ■

■ 14 Sections  •  Part V of 5 ■

Follows Chapter 11: Generating Functions  ·  Prepares students for Chapter 13: Designs, Finite Structures, and Symmetry

Chapter 12 — Front Matter

Purpose and Overview

This chapter connects the combinatorial tools developed in previous chapters to a new kind of mathematical object: the graph. In everyday language, the word "graph" often means a chart showing data over time. In mathematics, a graph is something different — a collection of objects and the relationships between them.

Graphs appear everywhere. A map of airline routes is a graph: airports are objects, and flight paths are relationships. A social network is a graph: people are objects, and friendships are relationships. A circuit board is a graph: components are objects, and wires are relationships. A scheduling problem is a graph: tasks are objects, and conflicts are relationships.

Combinatorics enters graph theory through counting. How many edges can a graph have? How many paths exist between two locations? How many ways can a network be arranged without conflicts? How many trees can be built on a given number of vertices? These are counting questions, and they require the same careful reasoning practiced in every chapter of this book.

Opening Question

A city has seven neighborhoods. The city council wants to build roads so that every neighborhood is directly connected to every other neighborhood by exactly one road. How many roads would need to be built? Before you can answer, you need to know how to represent the problem. The neighborhoods are objects. The roads are relationships between pairs of objects. By the end of Section 12.5, you will see exactly how this connects to combinations — and to a classical graph structure called the complete graph.

14Sections
14Objectives
30+Key Terms
12+Worked Examples

Learning Objectives

  1. 1Define a graph in terms of vertices and edges and represent small graphs in multiple ways.
  2. 2Count the vertices and edges of a graph and identify its order and size.
  3. 3Compute and interpret vertex degrees.
  4. 4State and apply the Handshaking Lemma to find edge counts and analyze degree sequences.
  5. 5Count edges in complete graphs and connect this count to combinations.
  6. 6Count edges in bipartite graphs and complete bipartite graphs.
  7. 7Define paths, cycles, and related concepts and count small examples.
  8. 8Define trees, identify their key combinatorial properties, and apply Cayley's Formula.
  9. 9Understand the concept of spanning trees as an introduction to larger ideas.
  10. 10Describe graph coloring as a combinatorial constraint problem and compute small chromatic numbers.
  11. 11Count the number of labeled graphs on n vertices and on n vertices with exactly m edges.
  12. 12Connect graph counting to applications in computing, scheduling, and network design.
  13. 13Recognize and avoid common graph counting mistakes.
  14. 14Prepare for designs, symmetry, and finite structures in Chapter 13.
Chapter 12 — Contents

Sections at a Glance

Sections 12.1 – 12.3
Graphs as Structures: Vertices, Edges, and Degrees
Combinatorial Definition · Order and Size · Degree Sequences
Section 12.1

Graphs as Combinatorial Structures

A graph is a finite mathematical structure built from two ingredients: a set of objects and a set of connections between those objects. In graph theory, the objects are called vertices and the connections are called edges.

Definition — Graph

A graph G consists of:

— a nonempty finite set V called the vertex set, whose elements are called vertices, and

— a set E called the edge set, whose elements are pairs of vertices called edges.

In a simple graph, every edge connects two distinct vertices, and no two edges connect the same pair of vertices. Unless stated otherwise, all graphs in this chapter are simple.

There are two standard ways to represent a graph. As a diagram: draw a dot for each vertex and a line between two dots whenever those vertices are connected by an edge. The exact positions of the dots do not matter — only which pairs are connected. As a vertex and edge list: write the vertex set V and edge set E explicitly. The edge connecting vertex u and vertex v is written {u, v} or sometimes uv.

Example 12.1.1
A four-vertex graph — vertex and edge list
  • RepresentLet V = {A, B, C, D} and E = {{A,B}, {B,C}, {C,D}, {A,D}}.
  • DescribeThis graph has 4 vertices and 4 edges. Vertex A connects to B and D. Vertex B connects to A and C. Vertex C connects to B and D. Vertex D connects to C and A.
  • DiagramDraw four dots in a square arrangement and connect adjacent corners. The result is a four-vertex cycle — a square with no diagonals.
Order: 4 vertices. Size: 4 edges. Structure: a 4-cycle.
Graphs and Combinations

Every edge is a 2-element subset of V. The total number of possible 2-element subsets of a set with n vertices is C(n, 2). This means the maximum number of edges in a simple graph on n vertices is C(n, 2) — achieved by the complete graph. This immediately connects graph structure to the combinations studied in Chapter 4.

Labeled vs. Unlabeled Graphs

In this chapter, all vertices are labeled — they have distinct names. Changing which specific vertices are connected gives a different graph, even if the visual shape looks similar. Counting unlabeled graphs (up to isomorphism) requires the symmetry tools of Chapter 13.

Section 12.2

Vertices and Edges

The two most basic counting questions about any graph are how many vertices does it have, and how many edges does it have? The order of a graph G is the number of vertices, written |V| or sometimes n. The size of a graph G is the number of edges, written |E| or sometimes m.

Graph NameDescriptionVerticesEdges
Path P₄Four vertices in a line: A – B – C – D43
Cycle C₄Four vertices in a square: A – B – C – D – A44
Star K₁,₃Center A connected to leaves B, C, D43
Complete K₄Every pair of 4 vertices connected46
Same Count, Different Structure

The path P₄ and the star K₁,₃ both have 4 vertices and 3 edges, but they are structurally different. Counting vertices and edges alone does not fully determine a graph's structure. The pattern of connections matters.

Section 12.3

Degree Counting

The degree of a vertex v, written deg(v), is the number of edges incident to v — that is, the number of edges that have v as an endpoint. In a diagram, the degree of a vertex equals the number of lines drawn from that dot.

GraphVertexDegreeSum of Degrees
Cycle C₄ (A – B – C – D – A)A, B, C, D each28
Star K₁,₃ (center A, leaves B, C, D)A (center)36
B, C, D each1
Complete K₄Every vertex312
Regular Graphs

A graph in which every vertex has the same degree k is called a k-regular graph. A cycle Cₙ on n vertices is 2-regular. The complete graph Kₙ is (n − 1)-regular, since every vertex connects to all other n − 1 vertices.

Sections 12.4 – 12.6
The Handshaking Lemma, Complete Graphs, and Bipartite Graphs
Double Counting · Kₙ Formula · Bipartite Structure and Kₚₙₘ
Section 12.4

The Handshaking Lemma

Theorem — The Handshaking Lemma

In any graph G = (V, E):

∑ deg(v) = 2 |E|

The sum of all vertex degrees equals twice the number of edges.

Proof

Every edge {u, v} contributes 1 to deg(u) and 1 to deg(v). So each edge contributes exactly 2 to the total sum of degrees. If there are |E| edges, the total sum is 2|E|. This is an instance of double counting — counting the same quantity two ways: by summing over vertices and by summing over edges.

□

Two important consequences follow immediately. First, the sum of all vertex degrees in any graph is always even. Second — and more striking — in any graph, the number of vertices with odd degree is always even. No matter what graph you draw, you can never have an odd number of odd-degree vertices.

Proof — Even Number of Odd-Degree Vertices

Let Vodd be vertices with odd degree and Veven those with even degree. Then:

∑ deg(Veven) + ∑ deg(Vodd) = 2|E|

The first sum (over even-degree vertices) is even. Since 2|E| is also even, the second sum must be even. A sum of odd numbers is even only when there is an even count of them. Therefore |Vodd| is even.

□
Example 12.4.1
Applying the Handshaking Lemma
  • ProblemA graph has 6 vertices with degrees 1, 2, 3, 3, 4, 5. How many edges does the graph have?
  • ThinkThe Handshaking Lemma says the sum of degrees equals twice the number of edges.
  • Count ∑ deg(v) = 1 + 2 + 3 + 3 + 4 + 5 = 18 2|E| = 18 ⟹ |E| = 9
  • CheckOdd-degree vertices: 1, 3, 3, 5 — four of them. Four is even. Consistent with the Handshaking Lemma.
Answer: The graph has 9 edges.
Example 12.4.2
A degree sequence puzzle
  • ProblemIs there a simple graph with 5 vertices, all having degree 3?
  • CountIf all 5 vertices have degree 3, the sum of degrees is 5 × 3 = 15. The Handshaking Lemma requires this sum to be even. But 15 is odd. Contradiction.
  • InterpretNo such graph exists. The Handshaking Lemma rules it out without any attempt to construct it.
Answer: No. A 3-regular graph must have an even number of vertices.
Section 12.5

Counting Edges in Complete Graphs

The complete graph on n vertices, written Kₙ, is a simple graph in which every pair of distinct vertices is connected by exactly one edge. Each edge in Kₙ corresponds to a 2-element subset of the vertex set. The number of such subsets is C(n, 2).

Edge Count Formula — Complete Graph

|E(Kₙ)| = C(n, 2) = n(n − 1) / 2

Each vertex connects to n − 1 others. Summing over all n vertices gives n(n − 1). Dividing by 2 corrects for counting each edge twice (once from each endpoint).

nGraphC(n, 2)EdgesEach vertex has degree
2K₂111
3K₃332
4K₄663
5K₅10104
6K₆15155
7K₇21216
10K₁₀45459
Answer to the Opening Question

Seven neighborhoods, each directly connected to every other, form the complete graph K₇. The number of roads needed is C(7, 2) = 7 × 6 / 2 = 21 roads.

Example 12.5.1
Counting handshakes at a meeting
  • ProblemTwelve people attend a meeting. Each person shakes hands with every other person exactly once. How many handshakes occur?
  • RepresentPeople are vertices. Handshakes are edges. This is K₁₂.
  • Count |E(K₁₂)| = C(12, 2) = (12 × 11) / 2 = 66
  • CheckEach person shakes 11 hands. Sum: 12 × 11 = 132. Divide by 2 (each handshake counted twice): 132 / 2 = 66. ✓
Answer: 66 handshakes.
Section 12.6

Counting Edges in Bipartite Graphs

A bipartite graph is a graph whose vertex set can be divided into two groups — call them A and B — such that every edge connects a vertex in A to a vertex in B. No edge connects two vertices within the same group. Bipartite graphs model situations where two types of objects are connected to each other but not within their own type: students and courses, servers and clients, workers and jobs.

Edge Count Formula — Complete Bipartite Graph

The complete bipartite graph Km,n has m vertices on one side and n on the other, with every vertex on the left connected to every vertex on the right.

|E(Km,n)| = m · n

By the product rule: each of the m left vertices connects to each of the n right vertices.

mnGraphEdges
11K₁,₁1
14K₁,₄4
23K₂,₃6
33K₃,₃9
45K₄,₅20
Identifying Bipartite Graphs

A graph is bipartite if and only if it contains no odd-length cycles. A triangle (K₃) is not bipartite. A four-vertex cycle C₄ is bipartite. All trees are bipartite (they contain no cycles at all).

Example 12.6.1
Expanding a server–client network
  • ProblemA company has 3 servers and 7 clients, each server connected to each client. How many connections are there? If the company adds 2 more servers and 3 more clients, how many connections are in the expanded network?
  • Original K₃,₇ : 3 × 7 = 21 connections
  • ExpandedNow 3 + 2 = 5 servers and 7 + 3 = 10 clients. K₅,₁₀ : 5 × 10 = 50 connections
Original: 21 connections. Expanded: 50 connections — more than double, because both sides grew.
Sections 12.7 – 12.9
Paths, Cycles, Trees, and Spanning Trees
Connectivity · Tree Properties · Cayley's Formula · Spanning Trees
Section 12.7

Paths and Cycles

Definitions — Path and Cycle

A path is a sequence of distinct vertices v₁, v₂, …, vk such that each consecutive pair {vi, vi+1} is an edge. The length of the path is k − 1 (the number of edges).

A cycle is a sequence of distinct vertices v₁, v₂, …, vk, v₁ where each consecutive pair (including the closing pair {vk, v₁}) is an edge. The length of the cycle equals the number of vertices k. A cycle requires at least 3 vertices.

A graph is connected if there is a path between every pair of vertices. A connected graph on n vertices has at least n − 1 edges.

A path visits each vertex at most once. This distinguishes a path from a walk, which may repeat vertices and edges. When counting paths, always clarify whether they are directed (the start and end are distinguished) or undirected (traversal in either direction counts as the same path). The problem's context determines which interpretation applies.

Example 12.7.1
Counting paths of length 2 in P₅
  • ProblemThe path graph P₅ has vertices A – B – C – D – E connected in a line. How many undirected paths of length 2 are there?
  • RepresentA path of length 2 uses two consecutive edges. List adjacent edge pairs: (AB, BC), (BC, CD), (CD, DE).
  • CountUndirected paths: A – B – C, B – C – D, C – D – E. Total: 3.
  • CheckDirected count: each undirected path gives 2 directed paths (e.g., A→B→C and C→B→A). Total directed paths: 6. Divide by 2 for undirected: 3. ✓
Answer: 3 undirected paths of length 2 in P₅.
Section 12.8

Trees and Basic Tree Counting

Definition — Tree

A tree is a connected graph with no cycles. Let T be a tree on n vertices. The following are all equivalent characterizations:

1. T is connected and has no cycles.

2. T is connected and has exactly n − 1 edges.

3. T has no cycles and has exactly n − 1 edges.

4. Any two vertices of T are connected by exactly one path.

5. T is connected, but removing any single edge disconnects it.

Theorem — A Tree on n Vertices Has n − 1 Edges

Proof by induction on n.

Base case (n = 1): A single vertex has 0 edges. And 1 − 1 = 0. ✓

Inductive step: Suppose every tree on k vertices has k − 1 edges. Consider a tree T on k + 1 vertices. Every tree with at least 2 vertices has at least one leaf — a vertex of degree 1. Remove a leaf v and its single incident edge. The resulting graph T′ has k vertices, is still connected, and still has no cycles. So T′ is a tree on k vertices; by the inductive hypothesis it has k − 1 edges. Adding back the removed edge: T has k edges. Since k = (k + 1) − 1, the formula holds.

□

A leaf is a vertex with degree 1. Every tree with at least 2 vertices has at least 2 leaves. A path graph has exactly 2 leaves; more branching trees have more. When a tree is given a designated starting vertex called the root, the tree acquires a natural parent–child hierarchy. Rooted trees are fundamental in computer science: file systems, binary search trees, and parse trees all use this structure.

Cayley's Formula

The number of distinct labeled trees on n vertices is:

nn − 2

For n = 2: 2⁰ = 1. For n = 3: 3¹ = 3. For n = 4: 4² = 16. For n = 5: 5³ = 125.

MGU Library Connection
  • Cayley's Formula and Prüfer sequences are developed in the MGU Graph Theory reference
  • The bijective proof is an example of the counting-by-bijection techniques in Chapter 9 of this textbook
  • Rooted tree applications appear in the MGU Data Structures and Algorithms chapters
Example 12.8.1
Using Cayley's Formula
  • ProblemHow many labeled trees can be formed using the vertex set {1, 2, 3, 4, 5}?
  • Count n = 5: n^(n − 2) = 5³ = 125
  • InterpretThere are 125 distinct labeled trees on 5 vertices. This large number for only 5 vertices illustrates how rapidly tree counts grow.
Answer: 125 labeled trees on 5 vertices.
Section 12.9

Spanning Trees as an Introduction

Definition — Spanning Tree

A spanning tree of a connected graph G is a subgraph that includes all vertices of G and is a tree (connected, no cycles). To form a spanning tree, keep all vertices but remove edges until no cycles remain and the graph stays connected.

Spanning trees arise naturally in network design. Connecting n locations using as few links as possible while keeping everything reachable requires a spanning tree: exactly n − 1 edges. Algorithms for finding minimum-cost spanning trees — such as Kruskal's and Prim's algorithms — are fundamental to internet routing, power grid design, and supply chain optimization.

Since Cayley's Formula counts all labeled trees on n vertices, it also counts spanning trees of Kₙ — the complete graph already contains all possible edges, so every labeled tree on those vertices is a valid spanning tree. For graphs other than Kₙ, counting spanning trees requires the Matrix-Tree Theorem, which is beyond this chapter.

Example 12.9.1
Spanning trees of K₃
  • ProblemFind all spanning trees of K₃ (vertices A, B, C with edges AB, BC, AC). Verify with Cayley's Formula.
  • RepresentA spanning tree must use all 3 vertices and exactly 2 edges (since a tree on 3 vertices has 3 − 1 = 2 edges).
  • Count Edges AB and BC : path A – B – C ✓ Edges AB and AC : path B – A – C ✓ Edges BC and AC : path B – C – A ✓
  • CheckCayley's Formula: n^(n − 2) = 3^(3 − 2) = 3¹ = 3. ✓
Answer: K₃ has exactly 3 spanning trees.
Sections 12.10 – 12.12
Graph Coloring, Network Configurations, and Applications
Chromatic Number · Chromatic Polynomials · Counting Graphs · Real-World Uses
Section 12.10

Graph Coloring as an Introduction

Graph coloring is the problem of assigning labels (called colors) to vertices so that no two adjacent vertices receive the same color. The chromatic number χ(G) of a graph G is the minimum number of colors needed for a valid coloring. Graph coloring has direct applications in scheduling, map coloring, register allocation in compilers, and frequency assignment in wireless networks.

GraphChromatic Number χ(G)Reason
Complete graph KₙnEvery vertex is adjacent to every other; all must differ
Bipartite graph (≥1 edge)2Two-sided structure allows 2-coloring
Tree (≥1 edge)2Trees are bipartite (no odd cycles)
Even cycle Cₙ (n even)2Bipartite; alternate colors around the cycle
Odd cycle Cₙ (n odd)3Not bipartite; third color needed to close the cycle
Chromatic Polynomial — Key Formulas

For the complete graph Kₙ with k available colors:

P(Kₙ, k) = k(k − 1)(k − 2)···(k − n + 1)

For a tree T on n vertices: P(T, k) = k(k − 1)^(n − 1)

For a cycle Cₙ on n vertices: P(Cₙ, k) = (k − 1)^n + (−1)^n (k − 1)

MGU Library Connection
  • Graph coloring, the Four Color Theorem, and chromatic polynomials are developed in the MGU Graph Theory reference
  • Scheduling applications using graph coloring appear in the MGU Operations Research lessons
  • Constraint satisfaction and graph coloring algorithms are covered in the MGU Algorithms chapter
Example 12.10.1
Counting colorings of a path
  • ProblemHow many proper colorings of the path P₄ (vertices A – B – C – D) exist using 3 available colors?
  • ThinkColor each vertex left to right. Each vertex cannot match its neighbor.
  • Count A : 3 choices B : must differ from A → 2 choices C : must differ from B → 2 choices D : must differ from C → 2 choices Total: 3 × 2 × 2 × 2 = 24
  • CheckUsing the tree formula: P(P₄, 3) = 3 × (3 − 1)^(4 − 1) = 3 × 2³ = 24. ✓
Answer: 24 proper 3-colorings of P₄.
Example 12.10.2
Counting colorings of an odd cycle
  • ProblemHow many proper 3-colorings does the cycle C₅ have?
  • FormulaP(C₅, k) = (k − 1)^5 + (−1)^5 (k − 1). Apply with k = 3: P(C₅, 3) = (3 − 1)^5 + (−1)^5 (3 − 1) = 2^5 + (−1)(2) = 32 − 2 = 30
  • CheckA path P₅ with 3 colors gives 3 × 2⁴ = 48 colorings. Closing into a cycle imposes one extra constraint, reducing the count. 30 < 48 is consistent.
Answer: 30 proper 3-colorings of C₅.
Section 12.11

Counting Network Possibilities

Beyond counting properties of a specific graph, combinatorics lets us count how many graphs of a certain type can be formed on a given vertex set. Each simple graph on vertex set V is determined by choosing which 2-element subsets of V to include as edges. There are C(n, 2) possible edges, each independently included or excluded.

Counting Labeled Graphs on n Vertices

Number of simple graphs on n labeled vertices: 2^C(n,2)

Number with exactly m edges: C(C(n,2), m)

Number of bipartite graphs between m and n vertices (any edge subset): 2^(mn)

nC(n, 2)Total simple graphs = 2^C(n,2)
101
212
338
4664
5101,024
61532,768
Example 12.11.1
Counting network configurations
  • ProblemA team is setting up a network of 5 computers. Each pair can be connected or not connected. How many distinct configurations are possible?
  • Count 2^C(5,2) = 2^10 = 1,024
Answer: 1,024 possible network configurations on 5 computers.
Example 12.11.2
Restricted network configurations
  • ProblemFrom those 5 computers, how many configurations use exactly 3 connections?
  • CountChoose 3 edges from 10 possible: C(10, 3) = (10 × 9 × 8) / (3 × 2 × 1) = 120
Answer: 120 configurations using exactly 3 connections.
Section 12.12

Graphs in Computing and Infrastructure

Graph counting underlies many of the systems that power modern technology and infrastructure. The structures studied in this chapter are not purely theoretical — they are directly applied in the following domains.

DomainGraph ModelCombinatorial Question
Computer NetworksRouters/servers as vertices; cables as edgesIs the network connected? How many paths between nodes?
File SystemsFiles/folders as vertices; parent-child as edges (a tree)Unique path to every file from root
SchedulingTasks as vertices; conflicts as edgesChromatic number = minimum time slots needed
Shortest PathsLocations as vertices; roads/links as edgesHow many edges in the minimum-length path?
Social NetworksPeople as vertices; relationships as edgesDegree distribution, clustering, path lengths
CryptographyGraph isomorphism, coloring hardnessCounting problems underlie protocol security
MGU Library Connection
  • Algorithms on graphs (DFS, BFS, Dijkstra's, Kruskal's) are developed in the MGU Computer Science Algorithms chapter
  • Graph-based cryptographic protocols appear in the MGU Cryptography lessons
  • Network flow and optimization are covered in the MGU Operations Research lessons on network models
  • Graph models in data science appear in the MGU Data Science Foundations lessons on network analysis
Sections 12.13 – 12.14
Common Mistakes and Preparing for What Comes Next
Ten Recurring Errors · Bridge to Chapter 13
Section 12.13

Common Graph Counting Mistakes

Mistake 1 — Forgetting to divide by 2 when using degree sums
A graph has degree sum 18, so it has 18 edges. Correct: |E| = (sum of degrees) / 2 = 18 / 2 = 9. Each edge contributes 2 to the degree sum.
Mistake 2 — Confusing vertex degree with total edge count
K₈ has 8 edges because each vertex has degree 7. Correct: K₈ has C(8,2) = 28 edges. The degree of each vertex (7) is not the total edge count.
Mistake 3 — Treating directed and undirected paths as equivalent
The path from A to B and the path from B to A are different paths, so I count both. Correct: In undirected graphs, paths A–B and B–A traverse the same edges. Clarify whether paths are directed or undirected before counting.
Mistake 4 — Assuming all trees are paths
Every tree must look like a straight line of vertices. Correct: A tree can branch. A star K₁,ₙ is a tree. A path is a tree, but trees can have any branching structure as long as they are connected and cycle-free.
Mistake 5 — Forgetting that a spanning tree requires all vertices
I found a tree subgraph inside G, so I have a spanning tree. Correct: A spanning tree must include every vertex of G. A tree subgraph that omits vertices is not a spanning tree.
Mistake 6 — Assuming every graph can be 2-colored
Every graph can be colored with 2 colors because there are only 2 choices at each step. Correct: A graph is 2-colorable if and only if it contains no odd cycles. Any triangle (K₃) requires 3 colors. C₅ requires 3 colors.
Mistake 7 — Applying Cayley's Formula to non-complete graphs
Any graph G on n vertices has n^(n−2) spanning trees. Correct: Cayley's Formula counts spanning trees of Kₙ specifically. For other graphs, different methods (like the Matrix-Tree Theorem) are needed.
Mistake 8 — Confusing number of graphs with number of edges
There are 2^C(n,2) edges in a graph on n vertices. Correct: 2^C(n,2) is the number of distinct labeled simple graphs on n vertices — not the edge count of any single graph.
Mistake 9 — Ignoring connectivity when applying tree results
Any graph with n − 1 edges is a tree. Correct: A graph with n − 1 edges is a tree only if it is also connected. A disconnected graph with n − 1 edges is not a tree.
Mistake 10 — Misidentifying bipartite structure
The graph K₃,₃ can be colored with 1 color since it is bipartite. Correct: Bipartite graphs need 2 colors (assuming at least one edge), not 1. The two sides receive different colors. χ(K₃,₃) = 2.
Section 12.14

Preparing for Designs and Finite Structures

Chapter 12 has introduced graphs as finite combinatorial structures built from vertices and edges. You have learned how to count vertices, edges, degrees, paths, cycles, trees, spanning trees, colorings, and network configurations. You have seen how counting formulas — particularly combinations — arise naturally in graph settings, and you have seen the Handshaking Lemma and Cayley's Formula as two of the deepest results in basic graph combinatorics.

In Chapter 13, you will move from graphs to combinatorial designs and finite structures with symmetry. Designs are arrangements of objects satisfying strict balance and regularity conditions. They include Latin squares, tournament schedules, block designs, and systems with finite geometric structure. Graphs and designs are related: a design is often described by a bipartite incidence graph, and many design problems are equivalent to graph coloring or matching problems.

The symmetry tools of Chapter 13 — group actions and Burnside's Lemma — also apply to graphs when you want to count unlabeled graphs (graphs up to isomorphism), which is a much harder and more subtle problem than counting labeled ones. The capstone chapter (Chapter 14) will bring graphs, designs, and all earlier combinatorial tools into a unified modeling framework.

Chapter 12 — Back Matter

Chapter Summary

Key Terms Review

graph
A mathematical structure of a vertex set V and edge set E of pairs of vertices, modeling relationships between objects.
vertex
A point in a graph; also called a node. The objects being related.
edge
A connection between two vertices. In a simple graph, a 2-element subset of V.
simple graph
A graph with no loops and no multiple edges between the same pair of vertices.
degree
The number of edges incident to a vertex. Written deg(v).
Handshaking Lemma
∑ deg(v) = 2|E|. The sum of all degrees equals twice the number of edges. A double-counting identity.
complete graph Kₙ
A simple graph on n vertices in which every pair is connected. Has C(n,2) edges and is (n−1)-regular.
bipartite graph
A graph whose vertices split into two groups with all edges crossing between groups. Characterised by having no odd cycles.
complete bipartite Kₘ,ₙ
A bipartite graph in which every vertex on one side connects to every vertex on the other. Has mn edges.
path
A sequence of distinct vertices where each consecutive pair is connected by an edge. Length = number of edges.
cycle
A closed path: a sequence of distinct vertices each connected to the next, and the last connected back to the first. Minimum length: 3.
connected graph
A graph in which a path exists between every pair of vertices. A connected graph on n vertices needs at least n − 1 edges.
tree
A connected graph with no cycles. Equivalent: a connected graph with exactly n − 1 edges. Any two vertices connected by exactly one path.
leaf
A vertex of degree 1 in a tree. Every tree with ≥2 vertices has at least 2 leaves.
spanning tree
A subgraph of a connected graph that includes all vertices and is itself a tree. Uses exactly n − 1 edges.
Cayley's Formula
The number of labeled trees on n vertices is n^(n−2). Also counts spanning trees of Kₙ.
graph coloring
An assignment of colors (labels) to vertices so that no two adjacent vertices share the same color.
chromatic number χ(G)
The minimum number of colors needed to properly color graph G.
regular graph
A graph in which every vertex has the same degree k; called k-regular.
subgraph
A graph formed from a subset of vertices and edges of a larger graph.

Chapter 12 Practice Problems

Part AGraph Vocabulary Practice
  1. Draw a simple graph on 4 vertices with exactly 3 edges. Is it connected? Is it a tree?
  2. Draw the complete graph K₅. Count its edges using the formula, then verify by listing each edge directly.
  3. Draw the complete bipartite graph K₂,₄. Count its edges.
  4. Which of the following is a tree? Explain your reasoning for each. (a) A graph on 5 vertices with 4 edges and no cycles. (b) A graph on 5 vertices with 5 edges and no cycles. (c) A graph on 5 vertices with 4 edges and one cycle.
  5. Give an example of: (a) a connected graph that is not a tree; (b) a tree that is not a path; (c) a bipartite graph that is also a tree.
Part BDegree Counting and the Handshaking Lemma
  1. A graph has degree sequence 1, 1, 2, 2, 2, 3, 3. How many edges does it have? How many vertices?
  2. Is there a simple graph with 6 vertices where every vertex has degree 5? Explain using the Handshaking Lemma.
  3. A graph has 8 vertices and the sum of all vertex degrees is 22. How many edges does it have?
  4. A 4-regular graph has 10 vertices. How many edges does it have?
  5. Prove: In any graph, the number of vertices with odd degree must be even.
Part CComplete and Bipartite Graphs
  1. How many edges does K₁₅ have?
  2. A social network has 50 users, each connected to every other. How many friendships?
  3. How many edges does K₃,₇ have?
  4. A company has 5 warehouses and 8 distribution centers, fully connected. How many connections?
  5. How many edges does K₄,₄ have? What is its chromatic number?
  6. A tournament has 12 players; each plays every other once. How many games are played?
Part DPaths, Cycles, and Trees
  1. How many edges does a tree on 20 vertices have?
  2. How many labeled trees on 6 vertices? Use Cayley's Formula.
  3. What is the minimum number of edges a connected graph on 10 vertices must have?
  4. A tree has exactly 3 leaves. What is the minimum number of vertices?
  5. Can a tree on n vertices have more than n − 1 edges? Prove your answer.
  6. How many spanning trees does K₄ have? List them by their edge sets, then verify with Cayley's Formula.
Part EGraph Coloring
  1. What is χ(K₇)?
  2. What is χ(C₆)? χ(C₇)?
  3. What is χ(T) for a tree on 10 vertices with at least one edge?
  4. How many proper 4-colorings of K₃ are there?
  5. How many proper 4-colorings of P₆ are there?
  6. Five courses share students. Conflict pairs: (A,B), (A,C), (B,D), (C,E), (D,E). What is the minimum number of time slots needed?
Part FCounting Graph Configurations
  1. How many simple graphs can be formed on 4 labeled vertices?
  2. How many simple graphs on 6 labeled vertices have exactly 3 edges?
  3. How many bipartite graphs can be formed between 3 vertices on the left and 4 on the right?
  4. A network on 4 servers uses exactly 4 connections. How many configurations are possible?
  5. How many simple graphs on 5 vertices have at least 8 edges?
Part GProof and Reasoning
  1. Prove that the complete graph Kₙ has C(n, 2) edges using a double-counting argument.
  2. Prove that in any simple graph on n vertices, there are at least two vertices with the same degree. (Hint: pigeonhole principle.)
  3. Prove that every tree with at least 2 vertices has at least 2 leaves. (Hint: consider the longest path.)
  4. Use the Handshaking Lemma to prove that a graph where every vertex has degree exactly 3 must have an even number of vertices.
  5. A connected graph on n vertices has exactly n edges. Prove it contains exactly one cycle.
Part HApplications
  1. A telecommunications company must connect 10 towns so every town is reachable from every other, using as few fiber-optic cables as possible. What is the minimum number? What structure do they form?
  2. A food web has 6 species as vertices and 9 edges indicating predator–prey relationships. What is the sum of all degree values?
  3. A logistics company wants to connect 7 warehouses so every pair has a path between them with the fewest direct links. What is the minimum, and what structure is formed?

Error Analysis

Each problem shows a student's incorrect reasoning. Identify the mistake and write the correct answer.

Problem 1
"K₈ has 8 edges because each vertex connects to the next one in a line."

What is the error? What is the correct edge count for K₈?

Problem 2
"I summed all the vertex degrees and got 30, so the graph has 30 edges."

What is wrong? How many edges does the graph actually have?

Problem 3
"A graph on 6 vertices with 5 edges must be a tree."

Is this always true? What additional condition is needed? Give a counterexample.

Problem 4
"K₄,₄ is bipartite, so its chromatic number is 1."

Explain the error. What is χ(K₄,₄) and why?

Problem 5
"The cycle C₉ is a cycle, so 2 colors are enough to color it properly."

Identify the error. What is χ(C₉) and why?

Chapter 12 Checkpoint

Chapter 12 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 12
Part A — Core Concepts
  1. State the Handshaking Lemma in your own words and explain why it is true using a double-counting argument.
  2. State two equivalent characterizations of a tree other than "connected and acyclic."
  3. What is the chromatic number of K₆? Explain why no fewer colors suffice.
  4. What does Cayley's Formula count, and what is the formula?
Part B — Computation
  1. A graph has 9 vertices with degrees 4, 4, 4, 3, 3, 3, 2, 2, 1. How many edges does it have?
  2. How many labeled trees are there on 7 vertices?
  3. How many simple graphs on 5 labeled vertices have exactly 6 edges?
  4. How many edges does K₅,₆ have?
  5. How many proper 3-colorings does the path P₅ have?
  6. How many edges does K₉ have?
Part C — Application and Reasoning
  1. A company is connecting 12 offices in a network using as few cables as possible while keeping all offices reachable from any other. What is the minimum number of cables, and what structure do they form?
  2. A graph on 8 vertices is 3-regular. Does a valid degree sequence exist? If so, how many edges does it have?
  3. In a class of 30 students, every student exchanges exactly one message with every other student on the first day of class. How many messages are exchanged?
  4. A bipartite graph has 4 vertices on each side. What is the maximum number of edges? What is this graph called?
  5. A tree has degree sequence 1, 1, 1, 1, 2, 2, 4. How many vertices and edges does it have?
Part D — Proof and Explanation
  1. Prove that in any simple graph on n vertices, the maximum degree any vertex can have is n − 1. Which graph achieves this maximum for all vertices simultaneously?
  2. A connected graph on n vertices has exactly n edges. Prove that it contains exactly one cycle.
  3. Explain why K₃,₃ requires exactly 2 colors. Could it ever be properly colored with 1 color? Why or why not?
Looking Ahead
Chapter 13: Designs, Finite Structures, and Symmetry

Chapter 12 introduced graphs as combinatorial structures. Chapter 13 will extend combinatorial reasoning to structured systems that obey strict balance and regularity conditions: Latin squares, tournament schedules, block designs, and finite geometric systems. Symmetry will become a central tool — when two arrangements of objects are considered "the same" under rotation or reflection, the number of distinct arrangements changes fundamentally. Burnside's Lemma will give you a precise method for counting under symmetry. Chapter 13 sets the stage for the capstone chapter, which brings together every major tool developed in this book.

MGU Library Connection
  • Graph Theory reference — Cayley's Formula, Prüfer sequences, Euler circuits, planarity, and chromatic polynomials
  • Discrete Mathematics, Chapter on Graph Theory — adjacency matrices, graph isomorphism, connectivity
  • Algorithms — DFS, BFS, Dijkstra's algorithm, Kruskal's algorithm, spanning tree construction
  • Probability and Statistics — random graphs and probabilistic graph models
  • Operations Research — network flow, minimum spanning trees, shortest-path optimization
  • Cryptography — graph-based protocols, isomorphism hardness assumptions
  • MGU Dictionary — entries for graph, tree, bipartite graph, chromatic number, spanning tree