# 7.1 Graph Terminology

> Vertices and edges, adjacency, degree, paths, cycles, connected graphs, weighted graphs, and how a tree is a special graph.

Chapter: Graphs · ~35 min · easy
URL: https://dsa.fetehadin.com/learn/graph-terms

## Mental 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.

## C++ code: graph-rep.cpp

```cpp
#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";
}
```

Expected output:

```text
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
```

## Complexity

| Case | Cost |
| --- | --- |
| max edges, undirected | V(V − 1)/2 |
| max edges, directed | V(V − 1) |
| sum of all degrees | 2E (each edge counted at both ends) |

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.

## Videos

- [Introduction to graphs](https://youtu.be/gXgEDyodOJU) (mycodeschool): Graph vocabulary with real examples (social networks, maps), and how graphs differ from trees.

## Exam 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.

## Quick check

1. A graph has degrees 2, 3, 2, 2, 3, 2. How many edges?
   A. 6
   B. 7
   C. 14
   D. 12
   Answer: B. Sum of degrees = 14 = 2E, so E = 7.

2. A connected graph with V vertices and no cycles has how many edges?
   A. V
   B. V − 1
   C. V + 1
   D. V²
   Answer: B. That is a tree.

3. Maximum edges in a simple undirected graph with 5 vertices?
   A. 5
   B. 10
   C. 20
   D. 25
   Answer: B. 5 · 4 / 2 = 10.

## Practice

**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.

Solution:

- 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]++;`.

**Problems:**

- [Find Center of Star Graph](https://leetcode.com/problems/find-center-of-star-graph/) (easy). Hint: The center is in every edge. Compare the first two edges.
- [Find the Town Judge](https://leetcode.com/problems/find-the-town-judge/) (easy). Hint: Count in-degree and out-degree. The judge has in = n − 1 and out = 0.

## Mastery checklist

- [ ] I can define every graph term and point to it on a drawing.
- [ ] I know the sum of degrees equals 2E.
- [ ] I can explain how a tree is a special graph.