Secondary 5 Graph Theory Worksheet
Graph theory rewards drawing before calculating, and these questions are built for that — degrees and the degree sum, chains, cycles and distance, modelling a situation as a graph, the chromatic number, the path of minimum value, the tree of minimum and of maximum value, and naming a graph as connected, simple, complete or a tree. The methods are explained in writing further down, and the printout is free.
Practice worksheet — free PDF
No email, no account, no watermark. Teachers: photocopy it for your classes freely. Worked solutions and 7 harder problems come with the Secondary 5 Math bundle.
1 of the 7 questions
Each question targets one named concept from the sheet. Read them here, or print the PDF — it has working space under each one. 1 of the 7 questions are printed below. The other 6 are built on a diagram or a table of values that does not translate to the page, so they are in the free PDF — marked below where they would have come.
-
Q1Chains and Cycles
This question is built around a diagram or a table of values. Open it in the PDF.
-
Q2Graphs
Six students of a robotics club recorded who they worked with during the term: Amina worked with Bruno, Clara and Dev; Bruno also worked with Clara; Clara also worked with Elin; Dev also worked with Elin; and Elin also worked with Farah. No other pair worked together.
- Model the situation with a graph. Say clearly what the vertices and the edges represent, then draw it.
- Give the degree of each vertex.
- Without recounting the edges one by one, use the degrees to find the number of edges. Check your answer against your drawing.
-
Q3The Chromatic Number
This question is built around a diagram or a table of values. Open it in the PDF.
-
Q4The Path of Minimum Value
This question is built around a diagram or a table of values. Open it in the PDF.
-
Q5The Tree of Minimum or Maximum Values
This question is built around a diagram or a table of values. Open it in the PDF.
-
Q6Types of Graphs
This question is built around a diagram or a table of values. Open it in the PDF.
-
Q7Synthesis — drawing on several sheets in this topic
This question is built around a diagram or a table of values. Open it in the PDF.
The 7 challenge problems for this topic are a separate, paid sheet and are not reproduced here.
Which stream is this for? This sheet is built for SN. It assumes you can model a situation as a graph and work with degrees, colouring, paths of minimum value and trees of minimum value, and it goes to the depth that program expects.
How to do every concept on this sheet
This is the part worksheet sites usually leave out. Below is the actual reasoning behind each group of questions — not a full solution set, the decisions that get you to one. Read it before you start, or after you get stuck.
The degree sum: one identity, and it answers part of half the questions
The degree of a vertex is the number of edge-ends meeting it. Add the degrees of every vertex and you get twice the number of edges:
Σ deg(v) = 2 × (number of edges)The reason is worth one sentence, because the question usually asks for it: every edge has two ends, so every edge is counted once at each of its two endpoints — never more, never fewer. Q1(a) and Q2(c) both end on this identity, and Q2 says outright that you may not recount the edges one by one.
The mistake: counting edges off the drawing. In a picture where edges cross, two lines that intersect in the middle of the page are not a vertex, and it is astonishingly easy to count that crossing as an extra edge or to miss an edge hidden behind a label. The degree sum is the check: work out the degrees vertex by vertex, halve the total, and compare with your count. If they disagree, the drawing lied to you, not the identity.
The same identity is what lets you rule things out. An odd degree sum is impossible, so a network in which every one of an odd number of vertices has odd degree simply cannot exist — no amount of trying arrangements is needed.
Chain, cycle, simple: the vocabulary is the mark
Q1(b) asks two questions that look like one — "is it a cycle?" and "is it a simple cycle?" — and each needs its own justification. These four words are not interchangeable:
Naming a walk through a graph
Check them in this order. Each condition adds to the one before it.
- 1Chain
Any sequence of vertices in which each consecutive pair is joined by an edge. Its length is the number of edges used, not the number of vertices. Nothing is forbidden — a chain may repeat vertices and edges freely.
- 2Simple chain
A chain that repeats no vertex. Since a repeated edge would repeat its endpoints, a simple chain automatically repeats no edge either.
- 3Cycle
A chain that starts and finishes at the same vertex and repeats no edge. The starting vertex being also the arrival vertex is required, not a violation.
- 4Simple cycle
A cycle that repeats no vertex either — apart from the start, which is necessarily also the finish. This is the exception you must state explicitly when you justify, because otherwise it looks like a repeated vertex.
The distance d(A, C) in Q1(c) is the length of the shortest chain from A to C, and a complete answer has two halves. You must show that no shorter chain exists — if there is no edge AC, then d(A, C) ≠ 1 — and you must exhibit an actual chain of the length you claim. Giving only the chain proves the distance is at most that; giving only the argument proves it is at least that. Both halves, every time.
Modelling a situation as a graph (Q2)
Q2 hands you sentences about who worked with whom and asks for a graph. Before drawing anything, write the two sentences the question explicitly asks for: the vertices are the students and an edge joins two students exactly when they worked together. That "exactly when" matters — it is what makes the drawing a faithful model rather than a doodle, and it is what tells you that a pair not mentioned gets no edge.
A practical habit: list the edges as unordered pairs before you draw, then draw from the list. Working the other way round — drawing first, listing afterwards — is how a pair gets drawn twice or forgotten.
The chromatic number needs two arguments, not one
The chromatic number χ is the smallest number of colours that lets you colour every vertex so that no edge joins two vertices of the same colour. Q3 splits the work into its two honest halves, which is exactly how it will be marked.
Lower bound — why you need at least k. Find a set of vertices that are pairwise joined. Three vertices all joined to each other need three different colours; four such vertices need four. Naming that set and checking that all its pairs are edges is a complete proof that χ ≥ k.
Upper bound — why k is enough. Produce an actual colouring with k colours and check every edge. Listing "colour 1: A, F; colour 2: B, D; colour 3: C, E" and then walking the edge list confirming each one joins two different colours is the whole proof.
Only when you have both do you get to write χ = k.
The mistake: "I found a colouring with three colours, so the chromatic number is 3." That shows three colours suffice. It says nothing about whether two would have done, and a student who never checks will confidently give 4 for a graph whose chromatic number is 3. The lower-bound half is the half people skip.
Practical way to colour: take the vertices in decreasing order of degree, give each the lowest-numbered colour not already used by one of its neighbours. It will not always find the true minimum in general, but on the graphs at this level it does, and it stops you from wandering.
The path of minimum value (Q4)
You want the cheapest route from A to F in a graph whose edges carry values. Do not hunt for routes and compare them; there are too many, and the trap in Q4 is precisely that the obvious-looking route is not the cheapest.
Labelling the graph, vertex by vertex
Each vertex gets one number: the smallest total value needed to reach it from the start.
- 1Label the start 0
Nothing is spent to be where you already are.
- 2Settle the cheapest unsettled vertex
Among the vertices you can reach, the one with the smallest label cannot be improved by any longer detour, because every edge adds a positive value. Fix it.
- 3Update its neighbours
For each neighbour, compare its current label with (this vertex's label + the edge value) and keep the smaller. Write down which edge gave the winning value — that is how you recover the route at the end.
- 4Repeat until the destination is settled
Then read the route backwards through the winning edges you recorded.
Why the first edge is not the answer. The cheapest edge leaving the start need not be on the cheapest route, and the cheapest route to a vertex is not always the direct edge to it. In Q4 the direct edge from A to B costs more than going round through C — so the label on B is the detour, not the edge. Always take the minimum of the two candidates rather than the one you happened to write first.
The tree of minimum value (Q5)
A different question, and a different algorithm, even though both are called "minimum". Here you want a network that keeps every vertex connected, at the smallest total value. The method is greedy and refuses cycles:
Building the tree
Sort, then walk the list once.
- 1Sort every edge by value, cheapest first
Write the sorted list before you choose anything. Half the errors on this question are a value read out of order.
- 2Take the next edge unless it closes a cycle
An edge closes a cycle exactly when both of its endpoints are already joined to each other by the edges you have taken. If so, refuse it and move on — and say in your answer which cycle it would have closed, because that is the justification.
- 3Stop at n − 1 edges
A tree on n vertices has exactly n − 1 edges. Starting from one vertex, every edge you accept must bring in exactly one new vertex — otherwise it would join two vertices already connected and close a cycle. So n − 1 edges bring in the other n − 1 vertices, and that is the whole count.
- 4For the tree of maximum value, run the same procedure with the dearest edge each time
The rule "refuse anything that closes a cycle" is unchanged. Only the sort order flips.
One claim worth being careful about: it is not true that the most expensive edge of a network is always left out. If a vertex hangs off the rest of the graph by a single expensive edge, that edge is the only way to reach it and every connecting tree must contain it. What is true is that the most expensive edge of a cycle is never needed.
Naming a graph, with a count as the justification (Q6)
Four words, four one-line tests — and Q6 asks you to justify each with a count of edges, not with an impression of the drawing.
Connected: every pair of vertices is joined by some chain. Exhibiting one cycle that passes through all the vertices settles it in a line. Simple: no edge from a vertex to itself, and never two edges between the same pair. Complete: every pair of vertices is joined, which on n vertices means exactly n(n − 1)/2 edges — each of the n vertices joined to the other n − 1, with every edge counted from both ends, hence the division by 2. Tree: connected with no cycle, which on n vertices means exactly n − 1 edges. So a graph with more than n − 1 edges is not a tree, and naming one of its cycles is a second, independent justification.
Question 7: two "minimum" answers that are not the same network
The synthesis question asks for the cheapest network keeping all the lodges connected, then for the fastest route between two particular lodges, and then — part (c) — whether the second lives inside the first. The answer is no, and understanding why is the point of the whole sheet.
A tree of minimum value minimises the total value of the network. It makes no promise at all about the distance between any particular pair of vertices, and it will happily route you the long way round if that saves value elsewhere. A path of minimum value minimises the distance for one pair, and cares nothing for the total. Two different objectives, two different algorithms, two different answers — and part (c) is asking you to say that sentence.
Preview all 7 pages
Click any page to open the full PDF.
Getting the most out of it
Redraw the graph before you answer anything
Copy it once, big, with room to write a degree beside each vertex and a running label inside it. Every path-of-minimum-value question becomes bookkeeping the moment the labels have somewhere to live, and every degree question becomes reliable the moment the degrees are written down rather than recounted three times.
Write the refusal, not just the choice
When you build a tree of minimum value, note beside each rejected edge which cycle it would have closed. It costs a few words, it is what the justification marks are for, and it is the only way to catch the moment you refuse an edge that was actually safe.
Answer the "justify" half separately
Nearly every question here has an answer and a reason, and they are marked separately. Get in the habit of writing the number, then a new sentence starting with "because" — the degree sum is even, no shorter chain exists, these three vertices are pairwise joined. On this topic the sentence is usually worth as much as the number.
Want the solutions, or something more challenging?
The worksheet, the questions above and every explanation on this page stay free permanently. Three more PDFs exist for this topic — the worked answer key, a harder problem set, and the answer key to that. They come with the Secondary 5 Math Solutions Bundle, which is what keeps the rest of the series free.
What else exists for Graphs
Three PDFs · 10 pages · all three are in the bundle below.
- Answer key — 2 pages. All 7 questions worked step by step, including the restrictions and the justifications. Not a list of final answers.
- Challenge problems — 6 pages, 7 problems. A separate sheet at exam-plus difficulty covering the same 6 concepts. Harder than anything on the free sheet.
- Challenge answer key — 2 pages. Every challenge problem worked to the same standard, with the checks shown.
- PDF, letter size, print-ready.
The one thing that's for sale
Every Secondary 5 Math topic — the complete Solutions Bundle
One download, one payment, the whole program. Every answer key and every challenge set for all 21 Secondary 5 Math worksheet sets — including this one.
- Worked solutions, not answer lists — every step written out
- Covers the whole year's program at this level
- Less than the price of one hour of tutoring — for the entire year's solutions
Taking Secondary 1 Math as well? The Secondary 1 Math bundle covers all 15 of its sets — 45 PDFs, 182 pages — on the same terms.
Taking Secondary 2 Math as well? The Secondary 2 Math bundle covers all 14 of its sets — 42 PDFs, 181 pages — on the same terms.
Taking Secondary 3 Math as well? The Secondary 3 Math bundle covers all 11 of its sets — 33 PDFs, 154 pages — on the same terms.
Taking Secondary 4 Math as well? The Secondary 4 Math bundle covers all 17 of its sets — 51 PDFs, 154 pages — on the same terms.
Taking CEGEP Calculus I as well? The CEGEP Calculus I bundle covers all 8 of its sets — 24 PDFs, 82 pages — on the same terms.
Taking CEGEP Calculus II as well? The CEGEP Calculus II bundle covers all 8 of its sets — 24 PDFs, 90 pages — on the same terms.
Taking CEGEP Linear Algebra as well? The CEGEP Linear Algebra bundle covers all 7 of its sets — 21 PDFs, 82 pages — on the same terms.
Taking AP Calculus AB as well? The AP Calculus AB bundle covers all 8 of its sets — 24 PDFs, 126 pages — on the same terms.
Common questions
Is this worksheet really free?
Yes — the questions are on this page to read, and the PDF downloads directly, no email and no account. The one paid item is optional: the complete Secondary 5 Solutions Bundle, which covers every set at this level.
Why does the sum of the degrees equal twice the number of edges?
Because every edge has two ends, and each end contributes 1 to the degree of the vertex it touches. Adding all the degrees therefore counts every edge exactly twice. That also means the degree sum is always even, which is often enough on its own to prove that some requested network cannot exist.
How do I prove a chromatic number rather than just guessing it?
With two separate arguments. To show at least k colours are needed, find k vertices that are pairwise joined — they can share no colour. To show k are enough, give an actual colouring with k colours and check every edge joins two different ones. A colouring alone only proves that k suffice, never that fewer would not.
What is the difference between a cycle and a simple cycle?
A cycle returns to its starting vertex without repeating an edge. A simple cycle additionally repeats no vertex, apart from the starting vertex, which is also the arrival vertex — you have to say that exception out loud when you justify, otherwise it reads like a repetition.
Is the tree of minimum value also the fastest route between two vertices?
No, and this is the trap in the synthesis question. A tree of minimum value minimises the total value of the whole network; a path of minimum value minimises the distance for one specific pair. The cheapest network often forces a detour between two particular vertices, so the fastest route can use an edge the tree left out.
How do I find the path of minimum value without trying every route?
Label each vertex with the smallest total needed to reach it from the start, settling the cheapest unsettled vertex each time and updating its neighbours by comparing their current label with the label of the settled vertex plus the edge value. Record the winning edge at each vertex, and read the route backwards at the end.
Can teachers use this in class?
Yes. Print and photocopy it for your own classes freely — I just ask that the tutorinmontreal.ca footer stays on the page.
I'm stuck on one question. Can you help?
Yes — through one-on-one tutoring, in Montreal or online. Get in touch to arrange a session, or see the current rates.
← All 21 Secondary 5 Math worksheets · Secondary 1 Math series (15 sheets) → · Secondary 2 Math series (14 sheets) → · Secondary 3 Math series (11 sheets) → · Secondary 4 Math series (17 sheets) → · CEGEP Calculus I series (8 sheets) → · CEGEP Calculus II series (8 sheets) → · CEGEP Linear Algebra series (7 sheets) → · AP Calculus AB series (8 sheets) →