Graphs (Graph Theory) — Mathematics Knowledge System

Overview

A graph is a mathematical structure made of vertices (nodes) connected by edges. Graphs model networks of every kind — social connections, road maps, computer networks, dependency chains — anywhere relationships between discrete objects matter more than the objects' individual properties.

Intuition

Strip away everything except 'what connects to what' and you have a graph. A subway map doesn't need accurate distances to be useful — you just need to know which stations connect to which. That's a graph: dots (vertices) for stations, lines (edges) for direct connections, and none of the geographic detail matters for the structure itself.

Interactive Graph

Formal Definition

Definition

A graph G is an ordered pair of a vertex set and an edge set:

G = (V, E)

V is the set of vertices, E is the set of edges connecting pairs of vertices

E \subseteq \{ \{u,v\} : u, v \in V \}

For an undirected graph, each edge is an unordered pair of vertices

Notation

Notation	Meaning
$V$	Vertex set
$E$	Edge set
$\deg(v)$	Degree of vertex v — number of edges incident to it

Properties

Handshaking lemma

\sum_{v \in V} \deg(v) = 2|E|

Example: Every edge contributes exactly 2 to the total degree sum

Connected

\text{A graph is connected if there is a path between every pair of vertices.}

Tree

\text{A connected graph with no cycles; a tree on } n \text{ vertices has exactly } n-1 \text{ edges.}

Applications

Networks, dependency graphs (build systems, package managers), and web page link structures are all graphs; graph algorithms (BFS, DFS, Dijkstra) are core CS curriculum.

Worked Examples

B is connected to A (via A-B) and C (via B-C), so it has 2 incident edges.
$\deg(B) = 2$

Answer: 2

Practice Problems

Difficulty 3/10

A tree has 12 vertices. How many edges does it have?

Difficulty 4/10

A computer network has 8 routers, and every router is directly connected to exactly 3 others. How many physical links (edges) are there?

Difficulty 4/10

In a social network modelled as an undirected graph, what does a user's 'degree' represent, and what does a high-degree node usually indicate?

Difficulty 5/10

A software build system represents tasks as a DIRECTED graph where an edge A→B means 'A must finish before B'. What graph property must hold for a valid build order to exist, and what algorithm produces the order?

Common Mistakes

Common Mistake

Confusing a 'path' (no repeated vertices) with a 'walk' (repeats allowed).

These terms are precise in graph theory: a walk can revisit vertices/edges, a trail can't repeat edges, a path can't repeat vertices at all.

Quiz

Flashcards

1 / 2

Historical Background

Graph theory began in 1736 when Leonhard Euler solved the Seven Bridges of Königsberg problem — proving it was impossible to walk through the city crossing each of its seven bridges exactly once — by representing the land masses as vertices and bridges as edges, the first known graph-theoretic argument. The field remained a curiosity for over a century before growing into a major branch of discrete mathematics in the 20th century, driven by applications in computer science and operations research.

1736
Euler solves the Seven Bridges of Königsberg problem, founding graph theory
Leonhard Euler
1852
The Four Color Conjecture is posed (proven 1976)
Francis Guthrie

Summary

A graph G = (V, E) consists of vertices and edges connecting them.
Degree of a vertex = number of incident edges; handshaking lemma: Σdeg(v) = 2|E|.
A tree is a connected, cycle-free graph with exactly n-1 edges on n vertices.
Graph theory began with Euler's 1736 solution to the Seven Bridges of Königsberg.
Foundational to networks, dependency resolution, and graph algorithms in computer science.

References

WebsiteWikipedia — Graph theory