Graph Terminology
Vertices and edges, adjacency, degree, paths, cycles, connected graphs, weighted graphs, and how a tree is a special graph.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
A map of cities and roads. The cities are vertices (nodes); the roads are edges. Unlike a tree, there is no root and no parent: any city can connect to any other, and you can drive in circles.
A graph is written G = (V, E): a set of vertices and a set of edges.
| Term | Meaning |
|---|---|
| Adjacent | two vertices joined by an edge |
| Degree | number of edges at a vertex |
| Path | a sequence of vertices joined by edges; its length is the number of edges |
| Cycle | a path that returns to its start without reusing an edge |
| Connected | there is a path between every pair of vertices |
| Weighted | each edge carries a number (distance, cost, time) |
| Directed | edges are one-way arrows (next topics) |
Trees are graphs too
A tree is a connected graph with no cycles. It always has exactly V − 1 edges. Add one more edge and a cycle appears.
The handshake rule
Every edge has two ends, so it adds 1 to the degree of two vertices. The sum of all degrees is therefore 2E. This is a favourite short-answer question.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Step through each term on one small graph, then on its directed twin.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <vector>
using namespace std;
const int V = 6;
int main() {
int edges[][2] = {{0, 1}, {0, 3}, {1, 2}, {1, 4}, {3, 4}, {2, 5}, {4, 5}};
int matrix[V][V] = {}; // O(V²) space
vector<vector<int>> list(V); // O(V + E) space
for (auto& e : edges) {
int u = e[0], v = e[1];
matrix[u][v] = matrix[v][u] = 1; // undirected: both directions
list[u].push_back(v);
list[v].push_back(u);
}
cout << "Adjacency matrix:\n ";
for (int j = 0; j < V; j++) cout << j << " ";
cout << "\n";
for (int i = 0; i < V; i++) {
cout << i << ": ";
for (int j = 0; j < V; j++) cout << matrix[i][j] << " ";
cout << "\n";
}
cout << "Adjacency list:\n";
for (int i = 0; i < V; i++) {
cout << i << " ->";
for (int v : list[i]) cout << " " << v;
cout << " (degree " << list[i].size() << ")\n";
}
cout << "edge 1-4? " << (matrix[1][4] ? "yes" : "no") << ", edge 0-5? " << (matrix[0][5] ? "yes" : "no") << "\n";
}Adjacency matrix: 0 1 2 3 4 5 0: 0 1 0 1 0 0 1: 1 0 1 0 1 0 2: 0 1 0 0 0 1 3: 1 0 0 0 1 0 4: 0 1 0 1 0 1 5: 0 0 1 0 1 0 Adjacency list: 0 -> 1 3 (degree 2) 1 -> 0 2 4 (degree 3) 2 -> 1 5 (degree 2) 3 -> 0 4 (degree 2) 4 -> 1 3 5 (degree 3) 5 -> 2 4 (degree 2) edge 1-4? yes, edge 0-5? no
05Complexity
| max edges, undirected | V(V − 1)/2 |
|---|---|
| max edges, directed | V(V − 1) |
| sum of all degrees | 2E (each edge counted at both ends) |
| Extra space | Depends on the representation (next topic) |
A graph with E close to V² is dense; with E close to V it is sparse. Road maps and social networks are sparse.
06Watch
Introduction to graphs
Why this one: Graph vocabulary with real examples (social networks, maps), and how graphs differ from trees.
07Exam lens
Likely questions
- Define: vertex, edge, adjacent, degree, path, cycle, connected graph, weighted graph.
- What is the maximum number of edges in an undirected graph with V vertices?
- Prove that the sum of the degrees of all vertices is 2E.
- How is a tree different from a general graph?
Common mistakes
- Counting path length in vertices instead of edges.
- Saying every graph is connected.
- Forgetting that a cycle must not reuse an edge.
08Quick check
09Practice
🟢 Trace by hand
Graph: V = {A, B, C, D, E}, E = {AB, AC, BC, CD}. Give the degree of each vertex, one cycle, a path from A to D, and say whether it is connected.
Show answer
- Degrees: A 2, B 2, C 3, D 1, E 0 (sum 8 = 2 × 4 edges)
- Cycle: A → B → C → A
- Path A → D: A → C → D (length 2)
- Not connected: E has no edges.
🟡 Implement it
Read V, E and E pairs of vertices. Print the degree of every vertex and say whether the sum equals 2E.
Hint
An int deg[V] array; each edge (u, v) does deg[u]++; deg[v]++;.
🔴 Solve problems
Hint
The center is in every edge. Compare the first two edges.
Hint
Count in-degree and out-degree. The judge has in = n − 1 and out = 0.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.