IMO (Maths Olympiad) /Combinatorics

Basic Definitions (Vertices, Edges, Paths, Cycles)

Graph Theory · free study notes

📚 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

  1. Draw a graph with 5 vertices and 6 edges.
  2. Find a path from one vertex to another that uses the fewest edges.
  3. Identify all cycles in your graph (if any).

Happy studying! 🚀

Your note

Page 1

Doubt hai is topic me?

Free AI teacher se poocho — 24/7, step by step.