Network Graphs
Explore graph theory: vertices, edges, degree sequences, paths, and Euler circuits. Understand how networks model real-world systems like roads, the internet, and social networks.
Vertices, Edges, and Basic Terminology
A network graph (or simply a graph) consists of vertices (nodes/points) connected by edges (links/lines). The graph can represent any system of connections.
Vertex (pl. Vertices)
A point in the graph. Represented by a circle or dot. Also called a node.
Edge
A line connecting two vertices. Can be directed (arrow) or undirected.
Degree
The number of edges meeting at a vertex. Written deg(V).
In this graph: 4 vertices, 6 edges, each vertex has degree 3
Paths, Trails, and Circuits
Understanding different types of routes through a network is fundamental to solving many real-world problems.
Path
A route through the graph where no vertex is repeated. A simple path visits each vertex at most once.
Trail
A route where no edge is repeated, but vertices may be revisited.
Circuit / Cycle
A path that starts and ends at the same vertex.
Euler Circuit
A circuit that uses every edge exactly once. Also called an Eulerian circuit.
Worked Example: Degree sequence
A graph has vertices A (degree 2), B (degree 3), C (degree 3), D (degree 2). Find the total number of edges.
Handshaking lemma: Sum of all degrees = 2 × number of edges
Sum of degrees = 2 + 3 + 3 + 2 = 10
Number of edges = 10/2 = 5 edges
Euler Circuits and the Handshaking Lemma
Euler Circuit Theorem (Euler, 1736)
A connected graph has an Euler circuit (traverses every edge exactly once and returns to the start) if and only if every vertex has even degree.
A connected graph has an Euler trail (traverses every edge once but does not return to start) if and only if it has exactly two vertices of odd degree.
Does this graph have an Euler circuit?
Graph: A-B, A-C, B-C, B-D, C-D (5 edges). Degrees: A=2, B=3, C=3, D=2.
Check: Vertices B and C have odd degree (3). Not all even.
Conclusion: No Euler circuit exists. But there are exactly 2 odd-degree vertices, so an Euler trail exists (from B to C or C to B).
Adjacency Matrix
A graph can be represented as a matrix where entry (i,j) = 1 if there is an edge between vertex i and vertex j, else 0.
| A | B | C | |
|---|---|---|---|
| A | 0 | 1 | 1 |
| B | 1 | 0 | 1 |
| C | 1 | 1 | 0 |
The complete graph on 3 vertices (triangle): every vertex connected to every other.
Key Vocabulary
Connected Graph
A graph where every vertex can be reached from every other vertex by following edges.
Handshaking Lemma
The sum of all vertex degrees equals twice the number of edges. This means the number of odd-degree vertices is always even.
Weighted Graph
A graph where each edge has a numerical weight (e.g. distance, cost, time). Used in shortest-path and minimum spanning tree problems.
Degree Sequence
The list of degrees of all vertices arranged in non-decreasing order, e.g. {1, 2, 2, 3} for a 4-vertex graph.
Knowledge Check
Test your knowledge of network graphs and graph theory.
Question 1
A vertex has 4 edges meeting at it. What is the degree of this vertex?
Question 2
A graph has 5 vertices with degrees 2, 2, 3, 3, 4. How many edges does this graph have?
Question 3
For an Euler circuit to exist in a connected graph, all vertices must have:
Question 4
What does an adjacency matrix represent in a network?
Question 5
A graph has vertices with degrees 2, 4, 2, 4. Does an Euler circuit exist?
Key Concepts Summary
- ●A graph consists of vertices and edges. The degree of a vertex is the number of edges meeting at it.
- ●Handshaking lemma: Sum of all degrees = 2 × number of edges.
- ●An Euler circuit uses every edge exactly once and returns to the start. Requires all vertices to have even degree.
- ●An Euler trail uses every edge exactly once without returning to start. Requires exactly two odd-degree vertices.
- ●An adjacency matrix is a grid representation showing which vertices are connected.