📚 Study Notes – Basic Definitions in Graph Theory
(Suits the “IMO Combinatorics” prep. All terms are explained with everyday analogies, short sentences, and a tiny example.)
1. What is a Graph?
- A graph is a picture made of dots and lines.
- The dots are called vertices (or nodes).
- The lines that connect two dots are called edges (or links).
Think of a graph like a map of a city:
- Vertices = Towns or intersections.
- Edges = Roads that connect those places.
2. Vertices
- Definition: A vertex is a single point in a graph.
- It has no size in the drawing – just a location.
- Every vertex can be labelled (A, B, C, …).
Analogy: A vertex is the name on a house – it marks a spot.
3. Edges
- Definition: An edge is a straight line that joins two vertices.
- It can be drawn in any way; we only care that it connects two points.
- An edge has no direction in a simple graph (you can walk both ways).
Analogy: An edge is a road that you can travel forward or back.
4. Paths
- Definition: A path is a sequence of vertices where each consecutive pair is joined by an edge, and no vertex is used twice.
- A path can have any length (number of edges).
- The start and end vertices are called the endpoints.
Analogy: A path is a simple walk from one town to another, never turning back to a place you already visited.
Tiny Example
Vertices: A – B – C – D (four towns in a line)
Edges: AB, BC, CD
A path from A to D is A → B → C → D.
Length of this path = 3 edges.
5. Cycles
- Definition: A cycle is a path that starts and ends at the same vertex, and all other vertices are distinct.
- A cycle must have at least three vertices (you need at least 3 roads to loop back).
- A cycle is often called a closed walk.
Analogy: A cycle is a round trip that brings you back to the starting town without revisiting any other town.
Tiny Example
Vertices: X, Y, Z
Edges: XY, YZ, ZX
Cycle: X → Y → Z → X
Length of this cycle = 3 edges.
6. Quick Summary
| Term | Everyday Analogy | Example |
|---|---|---|
| Vertex | Town / intersection | A, B |
| Edge | Road connecting towns | AB, BC |
| Path | A walk that never repeats a town | A → B → C |
| Cycle | A round trip back to start | A → B → C → A |
Remember:
- Vertices are points.
- Edges are connections.
- Paths are non‑repeating walks.
- Cycles are closed paths (start = end).
7. Practice Your Understanding
- Draw a graph with 5 vertices and 6 edges.
- Find a path from one vertex to another that uses the fewest edges.
- Identify all cycles in your graph (if any).
Happy studying! 🚀