Practice Flashcards
What 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 Flashcards in Topic 3.14
Below are all 8 flashcards for this topic. Sign up free to track your progress and get personalized review schedules.
3.14.18 cards
What are the two basic parts of a graph?
Vertices (the dots/points) and edges (the lines joining pairs of vertices).
What is the degree of a vertex?
The number of edge-ends meeting at that vertex (a loop counts as 2).
State the handshake lemma.
The sum of all vertex degrees equals 2 × (number of edges): Σ deg(v) = 2E.
Why must the number of odd-degree vertices be even?
Because the total degree Σ deg = 2E is always even, the odd degrees must pair up to keep the sum even.
What is a complete graph Kₙ, and how many edges does it have?
Every pair of vertices is joined; it has n(n − 1)/2 edges and every vertex has degree n − 1.
What is a tree, and how many edges does a tree on n vertices have?
A connected graph with no cycles; it has exactly n − 1 edges.
What is a bipartite graph?
The vertices split into two groups, with edges only between the groups (never within a group).
Distinguish a trail, a path and a cycle.
Trail = no repeated edge (may revisit a vertex); path = no repeated vertex; cycle = a path that returns to its start.
Topic 3.14 study notes
Full notes & explanations for Graph theory (HL only)
Math AI exam skills
Paper structures, command terms & tips
Want smart review reminders?
Sign up free to track your progress. Our spaced repetition algorithm will tell you exactly which cards to review and when.
Start Free