Basic Graph Terminology
Adjacent and Incident
Adjacent Vertices: Two vertices u and v are adjacent if there is an edge connecting them.
Example:
1 --- 2 --- 3- 1 and 2 are adjacent
- 2 and 3 are adjacent
- 1 and 3 are NOT adjacent
Incident: An edge e = {u, v} is incident with vertices u and v.
Neighborhood: The set of all vertices adjacent to v is called the neighborhood of v, denoted N(v).
Example:
2
/|\
1 | 4
\|/
3- N(2) = {1, 3, 4}
- N(1) = {2, 3}
- N(4) = {2, 3}
Degree
Definition: The degree of vertex v, denoted deg(v), is the number of edges incident to v.
Loop: A self-loop contributes 2 to the degree.
Isolated Vertex: A vertex with degree 0 (no edges).
Pendant Vertex (Leaf): A vertex with degree 1.
Regular Graph
Definition: A graph where all vertices have the same degree.
k-regular: All vertices have degree k.
Examples:
3-regular (cubic) graph: Every vertex has exactly degree 3.
Common Regular Graphs:
- 0-regular: Isolated vertices
- 1-regular: Perfect matching
- 2-regular: Collection of cycles
- 3-regular (cubic): Many interesting properties
- (n-1)-regular: Complete graph Kₙ
Paths and Cycles
Path
Definition: A sequence of vertices where each adjacent pair is connected by an edge, and no vertex is repeated.
Length: Number of edges in the path.
Example:
Graph:
1 --- 2 --- 3
| |
4 --- 5 --- 6Path from 1 to 6: 1 → 2 → 3 → 6
- Length: 3
- Vertices: 1, 2, 3, 6
Cycle (Circuit)
Definition: A path that starts and ends at the same vertex, with no other vertex repeated.
Example:
1 --- 2
| |
4 --- 3Cycle: 1 → 2 → 3 → 4 → 1 (Length: 4)
Acyclic Graph
Definition: A graph with no cycles.
Connectivity
Connected Graph
Definition: A graph is connected if there is a path between every pair of vertices.
Connected Component: A maximal connected subgraph.
Strongly Connected (Directed Graphs)
Definition: A directed graph is strongly connected if there is a directed path from every vertex to every other vertex.
Special Types of Graphs
1. Complete Graph (Kₙ)
Definition: Every pair of distinct vertices is connected by a unique edge.
Properties:
- n vertices
- n(n-1)/2 edges
- Every vertex has degree (n-1)
- Maximum possible edges
- (n-1)-regular
Examples:
K₃: Triangle (3 vertices, 3 edges) K₄: 4 vertices, 6 edges K₅: 5 vertices, 10 edges
2. Cycle Graph (Cₙ)
Definition: A graph consisting of a single cycle.
Properties:
- n vertices (n ≥ 3)
- n edges
- Every vertex has degree 2
- 2-regular graph
- Connected
Examples:
C₃: Triangle C₄: Square C₅: Pentagon C₆: Hexagon
3. Wheel Graph (Wₙ)
Definition: Formed by connecting a single vertex (hub) to all vertices of a cycle Cₙ.
Properties:
- (n+1) vertices
- 2n edges
- Hub vertex has degree n
- Rim vertices have degree 3
4. n-Cube (Qₙ) - Hypercube
Definition: Graph representing an n-dimensional cube.
Construction: Vertices represent n-bit binary strings; two vertices are connected if their strings differ in exactly one bit.
Properties:
- 2ⁿ vertices
- n×2ⁿ⁻¹ edges
- Every vertex has degree n
- n-regular
- Bipartite
Examples:
Q₁: Line segment (2 vertices, 1 edge) Q₂: Square (4 vertices, 4 edges) Q₃: Cube (8 vertices, 12 edges)
5. Bipartite Graph
Definition: A graph whose vertex set can be partitioned into two disjoint sets V₁ and V₂ such that every edge connects a vertex in V₁ to one in V₂.
Properties:
- No edges within V₁
- No edges within V₂
- All edges between V₁ and V₂
Characterization: A graph is bipartite if and only if it contains no odd-length cycles.
6. Complete Bipartite Graph (Kₘ,ₙ)
Definition: A bipartite graph where every vertex in V₁ (size m) is connected to every vertex in V₂ (size n).
Properties:
- m + n vertices
- m × n edges
- Vertices in V₁ have degree n
- Vertices in V₂ have degree m
Examples:
K₁,₃: Star with 3 leaves K₂,₃: 2+3 vertices, 6 edges K₃,₃: Utility graph (9 edges, famous in planarity)
7. Trees
Definition: A connected acyclic graph.
Properties:
- If n vertices, then (n-1) edges
- Unique path between any two vertices
- Removing any edge disconnects the graph
- Adding any edge creates a cycle
Applications:
- File systems
- Organization charts
- Decision trees
- Parsing expressions
8. Forest
Definition: A graph where every connected component is a tree.
Properties:
- Acyclic (no cycles)
- May be disconnected
- If n vertices, k components, then (n-k) edges
9. Planar Graph
Definition: A graph that can be drawn on a plane without edge crossings.
Euler’s Formula (for connected planar graphs): v - e + f = 2
Where:
- v = vertices
- e = edges
- f = faces (regions including outer region)
Examples:
- K₄ is planar
- K₅ and K₃,₃ are NOT planar
10. Subgraph
Definition: A graph G’ = (V’, E’) is a subgraph of G = (V, E) if V’ ⊆ V and E’ ⊆ E.
Induced Subgraph: Subgraph formed by selecting vertices and including all edges between them from original graph.
Spanning Subgraph: Subgraph that includes all vertices of G (V’ = V).
Degree Sequences
Definition: A list of vertex degrees, usually in non-increasing order.
Graphic Sequence: A sequence of numbers that can be the degrees of vertices in a simple graph.
Havel-Hakimi Algorithm
Used to determine if a sequence is graphic:
- Sort in decreasing order
- Remove first element d
- Subtract 1 from next d elements
- Repeat until all zeros or impossible
Key Points for Exams
- Deg(v) = number of edges at vertex v
- Regular graph: all vertices same degree
- Path: sequence of vertices, no repeats
- Cycle: path that returns to start
- Connected: path exists between all vertex pairs
- Complete graph Kₙ: n(n-1)/2 edges, all pairs connected
- Cycle Cₙ: n vertices, n edges, degree 2
- Bipartite: two sets, edges only between sets
- Tree: connected, acyclic, n vertices → (n-1) edges
- Planar: can draw without edge crossings
Practice Problems
-
Draw K₅ and verify it has 10 edges
-
Is C₆ a bipartite graph? Prove your answer.
-
How many edges does W₇ have?
-
Draw Q₃ (3-dimensional cube graph)
-
Given degree sequence (4, 3, 3, 2, 2), find sum of degrees and number of edges
-
In K₄,₅, what are the degrees of all vertices?
-
Can a tree have a cycle? Explain.
-
What is the degree sequence of C₈?
-
How many vertices does Q₄ have?
-
Is (5, 4, 3, 2, 1) a valid degree sequence? Why?