Practice Flashcards
Flip to reveal answersWhat are the two basic parts of a graph?
Track your progress — Sign up free to save your progress and get smart review reminders based on spaced repetition.
All 8 Flashcards — Introduction to graph theory
Sign up free to track progress and get spaced-repetition review schedules.
Question
What are the two basic parts of a graph?
Answer
Vertices (the dots/points) and edges (the lines joining pairs of vertices).
Question
What is the degree of a vertex?
Answer
The number of edge-ends meeting at that vertex (a loop counts as 2).
Question
State the handshake lemma.
Answer
The sum of all vertex degrees equals 2 × (number of edges): Σ deg(v) = 2E.
Question
Why must the number of odd-degree vertices be even?
Answer
Because the total degree Σ deg = 2E is always even, the odd degrees must pair up to keep the sum even.
Question
What is a complete graph Kₙ, and how many edges does it have?
Answer
Every pair of vertices is joined; it has n(n − 1)/2 edges and every vertex has degree n − 1.
Question
What is a tree, and how many edges does a tree on n vertices have?
Answer
A connected graph with no cycles; it has exactly n − 1 edges.
Question
What is a bipartite graph?
Answer
The vertices split into two groups, with edges only between the groups (never within a group).
Question
Distinguish a trail, a path and a cycle.
Answer
Trail = no repeated edge (may revisit a vertex); path = no repeated vertex; cycle = a path that returns to its start.
Read the notes
Full study notes for Introduction to graph theory
Topic 3.14 hub
Graph theory (HL only)
More from Topic 3.14
All flashcards in this topic
Math AI exam skills
Paper structures & tips
Track your progress with spaced repetition
Sign up free — Aimnova tells you exactly which cards to review and when, so you remember everything before your IB exam.
Start Free