Graphs and Networks: Definitions and Terminology

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.

---

Basic Definitions

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)

---

Degree of a Vertex

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
$\text{deg}(v)$deg(v)	Number of edges incident to vertex $v$v
In-degree	Number of edges directed into $v$v
Out-degree	Number of edges directed out of $v$v

The Handshaking Lemma

$\sum_{v \in V} \text{deg}(v) = 2|E|$∑v∈V​deg(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.

Worked Example

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.

---

Types of Graphs

Type	Definition
Complete graph $K_n$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 $K_{m,n}$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

Properties of Complete Graphs

$K_n$Kn​ has:

• $n$n vertices
• $\binom{n}{2} = \frac{n(n-1)}{2}$(2n​)=2n(n−1)​ edges
• Every vertex has degree $n - 1$n−1

$n$n	Vertices	Edges
3	3	3
4	4	6
5	5	10
6	6	15

---

Paths, Walks, and Cycles

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)

Eulerian and Hamiltonian Concepts

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.

---

Connectivity

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.

---

Subgraphs

A subgraph of a graph $G$G is a graph formed from a subset of the vertices and edges of $G$G. A spanning subgraph uses all vertices of $G$G.

---

Trees

A tree is a connected graph with no cycles. Key properties of a tree with $n$n vertices:

Property	Value
Number of edges	$n - 1$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$n vertices is $n^{n-2}$nn−2.

---

Planarity

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$V−E+F=2

where $V$V = vertices, $E$E = edges, $F$F = faces (including the outer face).

Kuratowski's theorem: A graph is planar if and only if it does not contain a subdivision of $K_5$K5​ or $K_{3,3}$K3,3​.

---

Summary

• Vertices and edges are the building blocks of graphs.
• The handshaking lemma: $\sum \deg(v) = 2|E|$∑deg(v)=2∣E∣.
• Complete graphs $K_n$Kn​: every pair connected, $n(n-1)/2$n(n−1)/2 edges.
• Trees: connected, acyclic, $n - 1$n−1 edges for $n$n vertices.
• Eulerian circuits exist iff all vertices have even degree.
• Planar graphs satisfy $V - E + F = 2$V−E+F=2.

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.