Learn the idea. Try it yourself.
Read the explanation or try 6 questions with hints. Free, untimed and no sign-in needed.
Original preparation lesson: use parity to reason about routes through a network. The starting applications suit students exploring the Netherlands first round. The constructive Euler-trail theory and general proofs are clearly labelled extensions. Every problem and diagram below was written for this lesson; none is presented as an official contest problem.
Your goal: distinguish edges from vertices, identify possible endpoints without guessing long routes, and prove a minimum stroke count by combining a lower bound with a construction.
Before you start: review odd and even numbers and double counting and degree sums if needed. No earlier graph-theory course is assumed. Proof methods supports the optional written extensions.
Study route: allow about 40–60 minutes for the diagnostics, Examples 1–3 with nearby practice, and Questions 1–6. This is a flexible study estimate. Take the minimum-stroke generalisation, Stretch questions and proof extensions in a separate sitting. These levels belong to this lesson; they are not official Dutch difficulty categories.
Three starting checks
NR-D1. Count edge ends at one vertex
A network has edges AB, AC, BC and CD. How many edges meet C?
Answer and repair route
Exactly AC, BC and CD meet C, so the answer is 3. The edge AB is elsewhere. If this count is uncertain, list the incident edges before using a formula; review counting edge ends.
NR-D2. What has been repeated?
A network contains AB, BC, CA and AD. Does the route A → B → C → A → D repeat an edge?
Answer and repair route
No. It uses AB, BC, CA and AD once each. Vertex A is visited again, but no edge is reused. Our route problems usually allow revisiting vertices. If a question forbids revisiting vertices, it is a different problem and the method below cannot simply be substituted.
NR-D3. Change two parities
Two distinct vertices have odd degrees. A new edge is added between them. What happens to their degree parities and to the degrees of every other vertex?
Answer and repair route
Each of the two endpoint degrees increases by 1, so both become even. Every other degree stays unchanged. If this is uncertain, review odd plus one and even plus one, then picture the two ends of one new edge.
Entering and leaving make pairs
Imagine drawing roads without lifting your pen and without tracing any road twice. At a junction in the middle of your route, arriving uses one road and leaving uses another. These used roads come in pairs. The starting and finishing junctions can each have one unpaired road. This pairing is the source of the parity test; it is more reliable than trying many long routes at random.
The objects and the rules
network, also called a graph, consists of vertices joined by edges. A vertex is a marked junction; an edge is one connection between two vertices. All our edges are undirected, so AB and BA name the same edge. We do not use loops from a vertex to itself. Parallel edges are distinct connections with the same endpoints and are allowed only when a question explicitly permits them.
trail follows adjacent edges without repeating an edge. Vertices may be visited repeatedly. A trail is closed when its start and end are the same vertex, and open when those vertices differ. A trail that uses every edge exactly once is an Euler trail. Drawing such a trail is what we mean by a one-stroke route.
In a minimum-stroke problem, every stroke is a nonempty trail, the strokes share no edge, and together they cover every edge. Between strokes the pen may be lifted and moved to any vertex. The goal counts strokes, not pen lifts. With at least one edge, two strokes require one lift between them.
Only marked dots are vertices. A crossing of lines without a marked dot is not a junction. Edge lengths, angles and the shape of a curved edge do not matter unless a question supplies a distance condition. Keep the stated edge list as the exact description of the network.
Count the edge ends
The degree of a vertex is the number of incident edges. Each edge contributes one to the degree at each of its two ends. Therefore the sum of all degrees is twice the number of edges. If a network has m edges, its degree sum is . This also proves that the number of odd-degree vertices is even: the sum of an odd number of odd integers is odd, whereas the full degree sum is even.
A necessary endpoint rule
In a trail, the used edges at every non-endpoint pair into arrivals and departures. If the trail is open, its starting and finishing vertices each have one unpaired used edge, so they have odd used degree; all other vertices have even used degree. If the trail is closed, even the start has its first departure paired with its final arrival, so every used degree is even.
When the trail covers the entire network, these used degrees are the original degrees. Consequently an open one-stroke route must start and finish at the two odd vertices. A closed one-stroke route requires every vertex to have even degree. Four or more odd vertices rule out a single stroke. These statements first give necessary conditions; we will prove the corresponding existence result below.
Parity does not connect separate pieces
A network is connected when a route of edges joins every pair of vertices. A connected component is one maximal connected piece. One continuous stroke cannot move from one component to another. For an all-edge route, all edges must belong to the same connected component. Isolated vertices have degree zero and no edge to draw, so they do not obstruct covering the edges elsewhere.
Our one-stroke criterion below assumes at least one edge and that all non-isolated vertices lie in one connected component. If there are no edges, no nonempty strokes are needed: the minimum is 0. An empty route at a chosen vertex may be described as a length-zero trail, but it is not counted as a drawing stroke here.
Worked example 1: find the endpoints, then construct a route
A network has edges AB, BC, CD, DA, DE and EC. Find the possible endpoints of a one-stroke route and exhibit such a route.
Planning hint 1 for NR-E1
Count the edges meeting each vertex before looking for a route.
Planning hint 2 for NR-E1
Exactly two vertices have an odd count. They must be the endpoints if a route exists.
The degrees of A, B, C, D and E are 2, 2, 3, 3 and 2. Thus an all-edge trail, if it exists, must start at C and end at D, or run in the reverse direction. The parity count restricts the endpoints; it does not by itself display a route.
Here is a construction: C → B → A → D → E → C → D. Its successive edges are CB, BA, AD, DE, EC and CD. These are precisely the six given edges, each once. Therefore the required trail exists, and its endpoints are C and D. Visiting C again near the end is allowed.
Your turn 1
Delete edge CD from Example 1. Can every remaining edge be drawn in one closed stroke? Give a route.
Hint 1 for NR-T1
Only the degrees at C and D change.
Hint 2 for NR-T1
Try following the five-sided outer boundary.
Full solution for NR-T1
C and D now both have degree 2, as do the other vertices. The route A → B → C → E → D → A uses the five remaining edges exactly once and returns to A. This explicit construction proves that one closed stroke works.
Worked example 2: prove that a stroke count is minimal
Four vertices are joined by all six possible pairwise edges. Find the fewest nonempty strokes that draw every edge exactly once.
Planning hint 1 for NR-E2
Each vertex has degree 3. How many distinct odd vertices can one stroke account for as endpoints?
Planning hint 2 for NR-E2
Try a five-edge trail first, leaving one edge as the second stroke.
All four degrees are odd. In a decomposition into strokes, an odd vertex must be an endpoint of at least one stroke: passages through it contribute pairs of edge ends, so they cannot alone account for an odd degree. Each stroke has only two endpoint positions. Thus at least two strokes are necessary.
Two suffice. Draw A → B → C → A → D → B, using AB, BC, CA, AD and DB. Then draw C → D, using the remaining edge. No edge occurs in both strokes, and all six are covered. The lower bound and this construction together prove that the minimum is 2. A failed attempt at one stroke would not, by itself, prove minimality.
Your turn 2
Delete AB from the four-vertex network in Example 2. Find a one-stroke route through the remaining five edges.
Hint 1 for NR-T2
The degrees of A and B become even; C and D remain odd.
Hint 2 for NR-T2
Start at C and keep the edge CD available until the end.
Full solution for NR-T2
The route C → A → D → B → C → D uses CA, AD, DB, BC and CD once each. Its endpoints are C and D, the two odd vertices. The construction also shows that deleting AB has not disconnected the remaining edges.
Extension: why the parity criterion is sufficient
For a finite network with at least one edge and all non-isolated vertices connected, the criterion is exact: all degrees even means a closed all-edge trail exists; exactly two odd degrees means an open all-edge trail exists between those two vertices. More than two odd degrees means no all-edge trail exists. The impossibility directions were proved by endpoint pairing. We now justify existence, rather than treating it as an unexplained rule.
First build a closed trail when all degrees are even. Start at any vertex incident with an edge and keep following unused edges. If you arrive at a vertex different from the start, the arrival has used an unpaired edge there. Because its original degree is even, an unused edge remains for you to leave; you cannot get stuck at that vertex. As there are finitely many edges, you eventually return to the start. Stop there to obtain a nonempty closed trail. You may return before every edge has been used.
Insert a further closed trail if edges remain. Removing the edges of a closed trail leaves even unused degree at every vertex, since the closed trail used arrivals and departures in pairs. Connectivity ensures that some vertex of the existing trail touches an unused edge whenever any edges remain: follow an original connecting route from the existing trail towards an unused edge and consider the first unused connection. Starting at such a vertex, the same even-degree argument gives another closed trail using only unused edges.
Insert the second trail at that shared vertex: follow the first trail up to the vertex, go around the second trail, return to the same vertex, and finish the first trail. The two edge sets are disjoint, so the inserted route repeats no edge. Repeat if necessary. Each insertion uses at least one new edge, and the graph is finite, so the process eventually covers every edge. This proves the all-even case constructively.
Now handle two odd vertices U and V. Add one temporary marked edge joining U to V. It may run alongside an existing edge; it is a separate edge for this proof. Both odd degrees become even, and the network stays connected. Construct a closed all-edge trail as above, then delete the temporary edge from its circular edge sequence. The rest is a trail through exactly the original edges, starting at one of U, V and ending at the other. Reverse its direction if needed. This proves the two-odd case.
The construction is not an instruction to choose an arbitrary first route and assume it covers everything. It explains what to do with unused edges after a first return, and why a place to insert them exists.
Worked example 3: join two closed pieces at a shared vertex
The network consists of the outer cycle A–B–C–D–E–F–A and the three further edges AC, CE and EA. Build a closed trail through all nine edges.
Planning hint 1 for NR-E3
The outer boundary is a closed trail, but using it alone leaves three edges.
Planning hint 2 for NR-E3
The three remaining edges form a closed trail at A. Insert that trail when the outer route visits A.
The degrees at A, C and E are 4; those at B, D and F are 2. The graph is connected and all degrees are even. The outer closed route A → B → C → D → E → F → A misses AC, CE and EA, so closing a route is not the same as finishing the task.
The unused edges form A → C → E → A. Insert this at A to obtain A → C → E → A → B → C → D → E → F → A. The first three edges are the inner triangle; the next six are the outer boundary. These edge sets are disjoint and together contain all nine edges. Repeated visits to A, C and E are useful here.
Your turn 3
In Example 3, begin by going along A → B → C. Insert the inner triangle at C, then complete the outer boundary. Write the full route.
Hint 1 for NR-T3
The inserted inner route must start and finish at C.
Hint 2 for NR-T3
Use C → E → A → C for the inserted triangle, then resume at C → D.
Full solution for NR-T3
The route is A → B → C → E → A → C → D → E → F → A. Its inner edges CE, EA and AC are each used once; its outer edges AB, BC, CD, DE, EF and FA are each used once. The insertion starts and ends at C, so it joins correctly to the outer route.
Extension: a general minimum-stroke rule
Assume the network is finite, has at least one edge, and all non-isolated vertices are connected. Suppose it has odd vertices, where k is a nonnegative integer. If , the proved even-degree result gives one stroke, and at least one is needed to draw any edge.
If , at least k strokes are needed. Every odd vertex must occur among the stroke endpoints an odd number of times, hence at least once. The distinct odd vertices therefore need at least endpoint occurrences, while each stroke supplies only two. This remains a lower bound if a stroke is closed or visits an endpoint again internally.
To attain the bound, pair the odd vertices into k pairs and add one temporary marked edge per pair. All degrees become even. Construct a closed trail in this augmented graph. Read it as a circular list of its edges in the order travelled; the edge following the last one is the first one again. Remove the k marked edges. Each remaining nonempty block begins immediately after one removed edge and ends before the next removed edge. Different blocks have different preceding removed edges, so there are at most k such blocks; if two removed edges are consecutive, the empty block between them is ignored. Each block remains a trail, and all the blocks together cover every original edge once. The lower bound says there cannot be fewer than k, so the minimum is exactly k.
Thus the minimum is one stroke for an all-even connected nonempty network, and half the number of odd vertices otherwise. Temporary edges are a proof device; they are removed before the original network is drawn. The formula is not applied across disconnected components. Solve each component containing edges separately, then add the stroke counts. A network with no edges needs zero strokes.
Worked example 4: six odd vertices do not mean six strokes
A square A–B–C–D–A has three extra edges AP, BQ and CR to three new vertices. Find the minimum number of strokes and exhibit a decomposition.
Planning hint 1 for NR-E4
Count the degrees of both the attachment vertices and the new ends.
Planning hint 2 for NR-E4
There are six odd vertices. Try using two longer trails and leaving one square edge for the third.
A, B and C have degree 3, P, Q and R have degree 1, and D has degree 2. The six odd vertices force at least three strokes. The network is connected, so the general rule gives three; we can also show a concrete construction.
Use P → A → B → Q, then R → C → D → A, then B → C. Their edge lists are PA, AB, BQ; RC, CD, DA; and BC. They are disjoint and cover all seven edges. Therefore the minimum is 3.
Your turn 4
Delete edge CR from Example 4. Vertex R is now isolated. What is the minimum number of strokes for the remaining edges? Give a construction.
Hint 1 for NR-T4
An isolated vertex has no edge to draw. Count odd degrees in the remaining edge-containing component.
Hint 2 for NR-T4
The odd vertices are now A, B, P and Q. Try one trail from P to Q and one from A to B.
Full solution for NR-T4
The remaining six edges form one connected component, plus the isolated R. Exactly A, B, P and Q are odd, so at least two strokes are needed. The trails P → A → D → C → B → Q and A → B use all six remaining edges once. Thus two strokes suffice. The isolated vertex R adds no stroke.
Changing the network: track exactly two vertices
Adding or deleting an edge changes the degree parity at exactly its two distinct endpoints. If both endpoints were odd, both become even; if both were even, both become odd; if one was odd, the odd status transfers to the other endpoint. A new edge cannot disconnect a graph, but removing one can. Always recheck connectivity after deletion.
If a route must start at a specified vertex and end at another, those two vertices must be the final odd vertices. Merely producing some pair of odd vertices does not satisfy prescribed endpoints. Count which vertices need their parity changed, use that to get a lower bound on edits, and then construct edits that attain it.
Check the first unsupported step
- “I revisited a vertex, so the route fails.” Check the edges instead. A trail may revisit vertices.
- “Every degree is even, so one stroke works.” First check that all edges lie in one connected component.
- “I reached the start, so I am finished.” Check for unused edges and insert a further closed trail at a shared vertex.
- “My lower bound is the answer.” Exhibit a construction or apply a proved existence argument.
- “Deleting an edge only changes parity.” It may also separate the graph.
- “Four odd vertices require four strokes.” A stroke has two endpoint positions. Count both and prove attainability.
Practise with feedback
The adaptive session selects six questions from the nine below. The static set provides two progressive hints and a specific repair link per question; the existing interactive engine uses its supported hint and worked feedback. Our practice questions have four options and are not a replica of the official first-round paper. Written proofs are reviewed with a rubric rather than automatically marked.
Interactive practice loads here. You can also use the complete question set below.
Nine graded original questions
Foundation checks the route language, degree count and endpoints. Core combines parity with connectivity or an edit. Stretch adds a family, a grid or prescribed endpoints. Keep a written reason for your choice. These exact questions and option order also form the adaptive bank.
NR-Q1. Choose the other endpoint
Foundation
A connected network has exactly the edges AB, AC, BC, CD, DE and EA. A route starts at A and uses every edge exactly once. At which vertex must it end?
- D
- E
Hint 1 for NR-Q1
Count the edges meeting each vertex. Passing through a vertex pairs an arrival with a departure.
Hint 2 for NR-Q1
The two odd-degree vertices must be the two distinct endpoints of a route using every edge once.
Answer and complete solution for NR-Q1
Answer B: C.
The degrees of A, B, C, D and E are 3, 2, 3, 2 and 2. Thus the only odd vertices are A and C. Starting at A forces the other endpoint to be C. A construction also confirms existence: A → B → C → A → E → D → C uses AB, BC, AC, AE, ED and DC once each.
Check the first error: A vertex may occur more than once in a trail. It is edges that may not be repeated.
NR-Q2. A repeated vertex can be useful
Foundation
A network consists of the two triangles ABC and CDE, sharing only vertex C. Which listed route uses all six edges exactly once?
- A → B → C → A
- A → B → C → A → C → D → E → C
- A → B → C → D → E → C → A
- A → B → C → D → C → E → C → A
Hint 1 for NR-Q2
Write the unordered edge used by each consecutive pair of vertices in a proposed route.
Hint 2 for NR-Q2
Returning to C is allowed. Using CD in both directions still repeats the same edge.
Answer and complete solution for NR-Q2
Answer C: A → B → C → D → E → C → A.
The route A → B → C → D → E → C → A uses AB, BC, CD, DE, EC and CA: precisely the six edges, with no repetition. It visits C twice, which is permitted. The first option omits triangle CDE; the second repeats AC; the fourth repeats CD and CE. Reversing an edge does not make it a different edge.
Check the first error: Do not confuse a trail with a route that is forbidden to revisit vertices.
NR-Q3. Do not infer an edge count from vertices alone
Foundation
A connected network has five vertices with degrees 4, 3, 3, 2 and 2. How many edges does it have?
- 5
- 6
- 7
- 14
Hint 1 for NR-Q3
Each edge has two ends, so it contributes to two degree counts.
Hint 2 for NR-Q3
Add the five degrees and divide by the number of ends contributed by each edge.
Answer and complete solution for NR-Q3
Answer C: 7.
The degree total is . Each edge is counted at both ends, so the number of edges is . The number of vertices alone would not determine the number of edges.
Check the first error: The degree sum counts edge ends, not edges.
NR-Q4. Even degrees in separate components
Core
A drawing consists of two disjoint triangles. No edge joins the triangles, and no new edge may be added. What is the fewest nonempty pen strokes that draw every edge exactly once? A pen lift may move to any vertex.
- 0
- 1
- 2
- 3
Hint 1 for NR-Q4
Even degrees do not join separate pieces of a network.
Hint 2 for NR-Q4
One continuous stroke stays within one connected component. Each triangle has its own closed one-stroke route.
Answer and complete solution for NR-Q4
Answer C: 2.
At least two strokes are necessary because one stroke cannot move between the two separate triangles. Two are sufficient: trace the first triangle once, lift the pen, and trace the second triangle once. Thus the minimum is 2. The all-even one-stroke criterion requires that all edges belong to one connected component.
Check the first error: Check connectivity before applying a parity criterion for one stroke.
NR-Q5. Repair a network for a closed route
Core
Four vertices are joined by one edge for every pair, giving six edges in total. What is the fewest additional edges needed so that all original and added edges can be drawn in one closed stroke? An added edge may join any two different vertices, including a pair already joined; parallel edges count separately.
- 1
- 2
- 3
- 4
Hint 1 for NR-Q5
Every original vertex has degree 3. A closed route needs all degrees even.
Hint 2 for NR-Q5
One additional edge changes the parity at exactly its two endpoints. Pair up the vertices that need to change parity.
Answer and complete solution for NR-Q5
Answer B: 2.
All four degrees are odd. Each added edge changes two degree parities, so at least two added edges are needed. Name the vertices A, B, C and D and add one extra AB edge and one extra CD edge. Every degree becomes 4, and the network remains connected. A direct closed route is A → B → C → D → A → C → D → B → A. The first AB and first CD use the original edges; the final BA and second CD use the added copies. The remaining steps use BC, DA, AC and DB once each. Thus all eight distinct edges are used exactly once, proving that two additions suffice. The minimum is 2. This construction is also consistent with the all-even criterion proved in the extension.
Check the first error: An open route can have two odd vertices; this question explicitly asks for a closed route.
NR-Q6. An edge removal can break connectivity
Core
Triangles ABC and DEF are joined only by the single edge CD. How many of the seven edges can be removed so that the remaining six edges can still be drawn in one continuous stroke, with no edge repeated?
- 2
- 3
- 4
- 6
Hint 1 for NR-Q6
Initially C and D are the only odd vertices. Removing an edge changes the parity at both of its ends.
Hint 2 for NR-Q6
Check the joining edge separately: its removal may pass a parity test but disconnect the remaining edges.
Answer and complete solution for NR-Q6
Answer C: 4.
Removing AC or BC changes C to even and creates an odd vertex at A or B; D remains odd. The remaining graph is connected, so either deletion gives a one-stroke route. Similarly, deleting DE or DF works. Deleting AB creates the four odd vertices A, B, C and D; deleting EF creates C, D, E and F. These cases cannot work. Deleting CD leaves two disjoint triangles, so it fails connectivity even though all remaining degrees are even. Exactly AC, BC, DE and DF work: 4 choices. Here are direct witnesses, so this conclusion does not depend on reading the extension. After deleting AC, use A → B → C → D → E → F → D. After deleting BC, use B → A → C → D → E → F → D. After deleting DE, use C → A → B → C → D → F → E. After deleting DF, use C → A → B → C → D → E → F. In each listed case, the six successive edges are exactly the remaining six edges, with no repetition.
Check the first error: Parity is not sufficient when a removed edge separates two components containing edges.
NR-Q7. Count which complete networks work
Stretch
For each integer n from 3 through 12, form a network of n vertices with exactly one edge joining each pair of different vertices. For how many values of n can every edge be drawn in one continuous stroke, either open or closed?
- 4
- 5
- 6
- 10
Hint 1 for NR-Q7
Every vertex has the same degree. Express that degree in terms of n.
Hint 2 for NR-Q7
Separate odd n from even n, and count how many odd vertices occur in each case.
Answer and complete solution for NR-Q7
Answer B: 5.
Every vertex is joined to the other vertices, so its degree is . The graph is connected. For odd n, all degrees are even and a closed one-stroke route exists. For even n, all n degrees are odd; since in this range, there are more than two odd vertices and no one-stroke route exists. The allowed values are 3, 5, 7, 9 and 11, giving 5 values. The small two-vertex exception is outside the stated range.
Check the first error: Count odd-degree vertices, not merely whether one particular degree is odd.
NR-Q8. Count the boundary junctions of a grid
Stretch
Twelve vertices form three rows and four columns. Join each vertex to every immediate horizontal or vertical neighbour, as shown, with no diagonal edges. What is the fewest nonempty pen strokes needed to draw every edge exactly once? A pen lift may move to any vertex.
- 2
- 3
- 4
- 6
Hint 1 for NR-Q8
Separate corner vertices, other boundary vertices, and interior vertices before counting degrees.
Hint 2 for NR-Q8
Corners have degree 2 and interior vertices degree 4. Count the remaining boundary vertices, then use the proved minimum-stroke rule.
Answer and complete solution for NR-Q8
Answer B: 3.
The four corners have degree 2. The top and bottom rows each have two noncorner vertices of degree 3, and the left and right sides each have one further noncorner vertex of degree 3. Thus there are odd vertices. The two interior vertices have degree 4. This grid is connected and has edges, so the proved minimum-stroke rule gives strokes. The lower bound comes from the six required odd endpoints, and the added-edge construction in the lesson proves that three suffice.
Check the first error: Do not count corner vertices again among the noncorner boundary vertices.
NR-Q9. Make a route with prescribed endpoints
Stretch
A connected network has exactly six vertices A, B, C, D, E and F. The degrees of A, B, C and D are odd; the degrees of E and F are even. What is the fewest additional edges needed to permit one trail that starts at E, ends at F and uses every original and added edge exactly once? Added edges may join any two distinct vertices; parallel edges are allowed and counted separately.
- 2
- 3
- 4
- 6
Hint 1 for NR-Q9
Write the required final parity at each of the six vertices. Which vertices must change parity?
Hint 2 for NR-Q9
Each added edge changes exactly two parities. For an attainable bound, pair the four initially odd vertices and deal separately with E and F.
Answer and complete solution for NR-Q9
Answer B: 3.
For an open trail from E to F, exactly E and F must have odd degree. Hence all six vertices must change parity: A, B, C and D must become even, while E and F must become odd. An added edge changes only its two endpoints, so at least edges are needed. Add AB, CD and EF. This changes each required parity once and preserves connectivity. The constructive two-odd-vertex criterion then gives a trail from E to F through every edge. Thus the lower bound 3 is attained.
Check the first error: It is not enough to leave any two vertices odd when the endpoints are prescribed.
Two optional written proof extensions
The Dutch first round asks for answers, not submitted proofs. These tasks develop the explanation behind the method and offer a bridge toward written mathematical reasoning. Each six-point rubric is this lesson’s self-review guide, not an official mark scheme.
NR-P1. An all-even connected network has no indispensable single edge
Let a finite connected network have at least one edge and an even degree at every vertex. Prove that deleting any one edge leaves the network connected. There are no loops; parallel edges, if present, count separately.
Hint 1 for NR-P1
Suppose deleting an edge separates the vertices into two nonempty groups with no remaining edge between them.
Hint 2 for NR-P1
In the original network, add the degrees of all vertices in one group. Internal edges contribute twice. How many contributions come from edges crossing to the other group?
Complete proof for NR-P1
Assume that deleting an edge UV disconnects the graph. Put all vertices reachable from U after deletion into a set S. The vertex V lies outside S; otherwise the deleted edge could be replaced by a route from U to V and the original connected network would still be connected. No remaining edge crosses from S to its complement, by the definition of reachability. Therefore the deleted edge UV was the only crossing edge in the original graph.
In the original graph, sum the degrees of vertices in S. Every edge whose two ends lie in S contributes 2, and the single crossing edge contributes 1. Thus this degree sum has the form for some nonnegative integer r, so it is odd. But every degree in S was even, making their sum even. This contradiction proves that deleting one edge cannot disconnect the graph.
The argument counts actual edges, including separate parallel edges. It does not confuse a crossing of drawn lines with a vertex. The conclusion is about deleting one edge; deleting several edges can disconnect an all-even network.
Six-point self-review rubric for NR-P1
- 1 point: Assumes a disconnection after deleting UV and defines one resulting vertex group.
- 1 point: Explains why UV was the only original edge crossing between the groups.
- 1 point: Counts each internal edge twice in the degree sum of that group.
- 1 point: Counts the single crossing edge once, making the sum odd.
- 1 point: Uses the original even-degree assumption to obtain a contradiction.
- 1 point: Concludes for every individual edge and does not extend the claim to deleting several edges.
Return to the worked bridge if a step needed help.
NR-P2. A family whose minimum number of strokes is forced
Let r be an integer with . Start with vertices and join every pair by one edge. Delete r edges whose endpoints are all different, leaving one vertex untouched by the deletions. Prove that the remaining edges can be drawn in exactly r nonempty pen strokes and cannot be drawn in fewer. Each remaining edge must be used once, and pen lifts may move to any vertex.
Hint 1 for NR-P2
Find the degree of a vertex touched by one deleted edge and the degree of the untouched vertex. Use the untouched vertex to check connectivity.
Hint 2 for NR-P2
For an explicit existence argument, temporarily restore the r deleted edges, construct an all-even closed trail, and then remove those marked edges from the trail.
Complete proof for NR-P2
Initially every vertex has degree , because it is joined to every other vertex. The deleted edges have distinct endpoints, so exactly vertices each lose one incident edge and acquire odd degree . The remaining vertex keeps the even degree . Each odd vertex must be an endpoint of at least one stroke, while a stroke supplies only two endpoint positions. Hence at least r strokes are necessary.
The untouched vertex is still adjacent to all the other vertices, so the remaining network is connected. To prove attainability without merely quoting a count, restore the deleted edges and mark them. The complete network has all degrees even and is connected, so the cycle-insertion construction gives a closed trail through every edge.
Read that closed trail as a circular list of its edges in travel order, then delete the r marked edges. Every remaining nonempty block starts immediately after a removed edge and ends before the next removed edge. Distinct blocks have distinct preceding removed edges, so there are at most r nonempty blocks; any empty block between consecutive removed edges is ignored. Each block is still a trail. Together they use every undeleted edge once, with no overlap, and therefore provide at most r strokes. Combined with the lower bound of r, this proves that exactly r strokes are necessary and sufficient.
The remaining network has edges because . The argument uses distinct endpoints of the deleted edges to obtain precisely odd vertices; without that condition, the parity count could change.
Six-point self-review rubric for NR-P2
- 1 point: Computes initial degree 2r.
- 1 point: Identifies exactly 2r odd vertices after the disjoint deletions.
- 1 point: Derives the lower bound r from endpoint counting.
- 1 point: Proves connectivity using the untouched vertex.
- 1 point: Constructs a closed trail after restoring the marked edges, using the proved even-degree result.
- 1 point: Cuts the circular trail at the r marked edges and combines upper and lower bounds.
Return to the worked bridge if a step needed help.
My proof notebook
State the network assumptions, count the relevant degrees, justify connectivity, and distinguish the lower bound from the construction. The rubric supports your own review; written proofs are not automatically marked.
A useful exit check
Explain why two disconnected triangles pass an even-degree test but still need two strokes. Then choose a Core question and solve it without hints, giving both the obstruction and a construction where needed. If you used the solution, revisit its repair link and retry later; remembering a route is different from understanding why it works.
How this supports Netherlands preparation
The official first-round archive currently provides the released paper from 19–30 January 2026 and its official solutions. Its tasks include parity and constrained-route reasoning. The first-round format is 120 minutes with eight five-option questions and four exact short answers. It does not ask students to submit proofs, and calculators and formula sheets are not allowed.
The exercises here are original topic practice, with a deliberate extension into Euler trails and proofs. They are not copied or translated from that paper, do not cover the full first-round topic range and are not endorsed by the organiser. For the current school entry route, use the Netherlands guide and the organiser’s first-round instructions. The 2026 released paper is practice evidence, not a future paper.
Choose your next step
For parity arithmetic, return to odd and even numbers. For counting edge ends, use double counting. To compare another kind of route problem, try lattice paths and blocked routes, where directed movement rules give a different method. For the written extensions, review proof methods.
Original teaching material · IMOolympiad.com. Report a specific error or unclear step. Learning progress is optional and stays in this browser.