You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
Graph theory is the mathematical study of networks — collections of points (vertices) connected by lines (edges). It is used to model everything from road networks and computer systems to social connections and scheduling problems. This lesson introduces the fundamental definitions and terminology you need for the entire Discrete Mathematics module.
| Term | Definition |
|---|---|
| Graph | A set of vertices (nodes) connected by edges (arcs) |
| Vertex (node) | A point in the graph |
| Edge (arc) | A connection between two vertices |
| Simple graph | A graph with no loops or multiple edges |
| Multigraph | A graph that may have multiple edges between the same pair of vertices |
| Directed graph (digraph) | A graph where edges have a direction |
| Weighted graph | A graph where edges have numerical values (weights) |
| Network | A weighted graph (weights often represent distances, costs, or capacities) |
The degree of a vertex is the number of edges incident to it. In a digraph, we distinguish between in-degree and out-degree.
| Type | Definition |
|---|---|
| deg(v) | Number of edges incident to vertex v |
| In-degree | Number of edges directed into v |
| Out-degree | Number of edges directed out of v |
∑v∈Vdeg(v)=2∣E∣
The sum of all vertex degrees equals twice the number of edges. This is because each edge contributes 1 to the degree of each of its two endpoints.
Corollary: The number of vertices with odd degree is always even.
A graph has vertices A, B, C, D, E with degrees 3, 2, 4, 3, 2.
Sum of degrees = 3 + 2 + 4 + 3 + 2 = 14. Number of edges = 14/2 = 7.
Odd-degree vertices: A (3), D (3). Count = 2 (even). Consistent with the handshaking lemma.
Exam Tip: The handshaking lemma is frequently used to check answers. If your sum of degrees is odd, you have made an error. Also, remember that the number of odd-degree vertices must be even.
| Type | Definition |
|---|---|
| Complete graph Kn | Every pair of vertices is connected by exactly one edge |
| Bipartite graph | Vertices can be split into two sets with edges only between (not within) the sets |
| Complete bipartite Km,n | Every vertex in one set is connected to every vertex in the other |
| Tree | A connected graph with no cycles |
| Forest | A collection of trees (a disconnected acyclic graph) |
| Planar graph | A graph that can be drawn in the plane without edge crossings |
Kn has:
| n | Vertices | Edges |
|---|---|---|
| 3 | 3 | 3 |
| 4 | 4 | 6 |
| 5 | 5 | 10 |
| 6 | 6 | 15 |
| Term | Definition |
|---|---|
| Walk | A sequence of vertices where consecutive vertices are connected by edges (edges may repeat) |
| Trail | A walk with no repeated edges |
| Path | A walk with no repeated vertices (hence no repeated edges) |
| Cycle | A closed path (starts and ends at the same vertex, no other vertices repeated) |
| Concept | Definition | Condition |
|---|---|---|
| Eulerian trail | A trail that uses every edge exactly once | Exactly 2 vertices have odd degree |
| Eulerian circuit | A closed trail that uses every edge exactly once | All vertices have even degree |
| Hamiltonian path | A path that visits every vertex exactly once | No simple condition (NP-complete problem) |
| Hamiltonian cycle | A cycle that visits every vertex exactly once | No simple condition |
Exam Tip: Eulerian properties depend on vertex degrees and are easy to check. Hamiltonian properties have no simple degree condition — you typically need to find the path/cycle by inspection.
A graph is connected if there is a path between every pair of vertices. A disconnected graph has two or more connected components.
A bridge is an edge whose removal disconnects the graph.
A cut vertex is a vertex whose removal (along with all its incident edges) disconnects the graph.
A subgraph of a graph G is a graph formed from a subset of the vertices and edges of G. A spanning subgraph uses all vertices of G.
A tree is a connected graph with no cycles. Key properties of a tree with n vertices:
| Property | Value |
|---|---|
| Number of edges | n−1 |
| Connected | Yes |
| Unique path between any two vertices | Yes |
| Adding any edge creates exactly one cycle | Yes |
| Removing any edge disconnects the tree | Yes |
Cayley's formula: The number of labelled trees on n vertices is nn−2.
A graph is planar if it can be drawn in the plane without any edges crossing.
Euler's formula for a connected planar graph:
V−E+F=2
where V = vertices, E = edges, F = faces (including the outer face).
Kuratowski's theorem: A graph is planar if and only if it does not contain a subdivision of K5 or K3,3.
Exam Tip: When describing a graph, always state the number of vertices, edges, and any special properties (connected, tree, Eulerian, etc.). Use precise terminology — examiners reward correct vocabulary.