KnowledgeInSight
What Mathematicians Do
0% of Course 5 complete

Module 2 · Lesson 1

Graph Theory: Counting arrangements and the bridges of Königsberg

You'll learn to count possibilities without listing them, and you'll solve the puzzle that started graph theory: whether a walk can cross each of seven bridges exactly once. You'll leave able to look at a network and say quickly whether it can be traced in one path.

What you will be able to do

  • Count arrangements with the multiplication principle and decide whether a network can be traced in one path.

0% of this lesson · 9 items · 1h 3m total · 48m without the optional problem set

Contents of this lesson9 items
  1. ReadingCan You Cross Every Bridge Exactly Once?3 min
  2. ReadingCounting and Networks from India and China to Euler4 min
  3. ReadingThe Multiplication Principle, Permutations, and Combinations4 min
  4. ReadingThe Pigeonhole Principle4 min
  5. ReadingGraphs and Euler's Rule for Tracing Every Edge4 min
  6. Guided ReadingWorked Example: Solving the Königsberg Bridges Problem7 min
  7. Guided ConversationTrace a Network in Your Neighborhood12 min
  8. Problem Set · optionalCounting and Tracing15 min
  9. Knowledge CheckCounting arrangements and the bridges of Königsberg10 min

Report an issue on this page

Reading 3 min Done

Can You Cross Every Bridge Exactly Once?

In the 18th century, the Prussian city of Königsberg (today's Kaliningrad, in Russia) sat on both banks of a river and on an island in the middle of it. Seven bridges joined four areas of land: the island, the north bank, the south bank, and a second piece of land to the east. People asked a question about them. Could you take a walk that crosses every bridge exactly once?

Try it before reading on. Here is the layout:

  • The island has two bridges to the north bank, two to the south bank, and one to the eastern land.
  • The north bank has one more bridge, to the eastern land.
  • The south bank has one more bridge, also to the eastern land.

That's seven bridges. You can start anywhere and end anywhere. You may walk across land as much as you like, but you may not cross any bridge twice, and you must cross all seven.

If you sketch it and try a few routes, a pattern sets in. You get across five or six bridges, then find yourself on a bank whose bridges you've already used. You back up and try another order. After a dozen attempts you still haven't found a route, but you also haven't shown that none exists. Maybe the right order is one you haven't tried.

This is where listing runs out. Seven bridges can be crossed in a great many orders, and checking them one by one is slow and easy to get wrong. A bigger city with more bridges would make the list hopeless.

In a paper presented to the St. Petersburg Academy of Sciences in 1735, Leonhard Euler settled the question without trying a single route. He said that solving it by listing every possible route would be laborious, and for larger layouts impossible (Euler 1741, §3). Instead, he counted. For each area of land, he counted the bridges that touch it. The island has five, and each of the other three areas has three.

Those four numbers are enough. Euler showed that a walk crossing each bridge exactly once can't exist when more than two land areas touch an odd number of bridges (Euler 1741, §20). Königsberg has four such areas, so no such walk is possible. Your failed attempts weren't bad luck. The walk you were looking for doesn't exist.

The answer also tells you something the attempts never could: it doesn't depend on lengths, distances, or the shape of the river. Only which areas each bridge connects matters. That idea, studying connections and ignoring measurement, became graph theory, the mathematics of networks.

Combinatorics and graph theory share this habit of mind. They answer "how many?" and "is it possible?" by finding a quantity that settles the question, rather than by listing every case. The same habit lets mathematicians count arrangements too numerous to write down and decide questions about networks with millions of connections.

References

  • Euler, Leonhard. 1741. "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Imperialis Petropolitanae 8 (dated 1736). Eneström E53.

Reading 4 min Done

Counting and Networks from India and China to Euler

Introduction

Counting arrangements sounds like a modern puzzle-book topic, but scholars in India, China, and Europe worked on it for centuries before anyone named the field. Network questions have a much more precise starting point: a single paper by Euler.

This reading covers counting in Indian poetics and mathematics, the arithmetic triangle in China and Europe, and Euler's paper on the bridges of Königsberg. Citations to Euler's paper use the paragraph numbers (§) that Euler gave it.

Counting Rhythms and Arrangements in India

Combinatorics is the branch of mathematics that counts, arranges, and selects objects, often without listing every possibility. Some of its early problems came from poetry. Sanskrit verse is measured in syllables that are either light or heavy, and a meter is a pattern of the two. The Chandaḥ-sūtra, a work on meter attributed to Pingala and dated to around the third or second century BCE, describes in compressed verse how many patterns a meter of a given length allows (Misra 2021).

The count works like this. A meter of four syllables, each light or heavy, has 16 possible patterns. Grouped by the number of heavy syllables, they come to 1, 4, 6, 4, and 1. Pingala's verses are terse, and the commentator Halayudha, writing around the 10th century CE, read them as a rule for building a triangle of numbers that gives these counts (Misra 2021; see also Katz 2018, sec. 8.6).

Counting arrangements of other things followed. Bhaskara II (1114–1185) devoted the final chapter of his Lilavati to combinations (O'Connor and Robertson 2000). He gave a rule for how many different numbers can be made by arranging a set of different digits: multiply together all the whole numbers from 1 up to the number of digits. Three digits give 1 \times 2 \times 3 = 6 numbers, and four give 24 (Mahesh et al. 2021).

The Arithmetic Triangle in China and Europe

The same triangle appears in Chinese mathematics. In 1261, Yang Hui wrote a detailed commentary on the classic Nine Chapters on the Mathematical Art. In it he gave the triangle up to its sixth row and said he had learned it from a treatise by Jia Xian. Jia Xian's own notes haven't survived, so they're known only through Yang Hui's references to them (O'Connor and Robertson 2003; Katz 2018, chap. 7).

In the 17th century, Blaise Pascal studied the triangle in his Treatise on the Arithmetical Triangle. He wasn't the first to study it, but his work on it was the most important on the topic, and the triangle is now widely called Pascal's triangle (O'Connor and Robertson 1996a). A name that doesn't credit a single person is the arithmetic triangle (Pascal's triangle): a triangle of numbers in which each entry is the sum of the two entries above it, and whose rows count the ways to choose items from a set.

The triangle can't be credited to one founder. It turns up in Indian, Chinese, and European work, centuries apart.

Euler and the Geometry of Position

Network questions have a sharper beginning. In 1735, Euler presented a solution to the Königsberg bridges puzzle to the St. Petersburg Academy, according to the Academy's minutes. The paper was printed in the Academy's volume for 1736, but that volume didn't appear until 1741 (Grötschel and Yuan 2012).

Euler placed the problem in what he called the geometry of position: a kind of geometry concerned with where things are and how they're connected, rather than with measurement. He said Leibniz had first named the field and that it was then almost unknown (Euler 1741, §1). The problem involved no lengths or angles, only which land areas each bridge connected. Euler reduced it to counting bridges at each area and showed that no walk can cross all seven bridges exactly once (Euler 1741, §20).

That shift, from measuring a layout to recording its connections, is the core of graph theory: the study of networks made of points and the connections between them, where only which points are connected matters, not distances or shapes. The paper is often treated as the birth of the field (Grötschel and Yuan 2012).

PeriodWhereContribution
c. 3rd–2nd century BCEIndiaPingala counts the patterns of poetic meters
c. 10th century CEIndiaHalayudha reads Pingala's rule as a triangle of counts
12th centuryIndiaBhaskara II gives a rule for counting arrangements of digits
1261ChinaYang Hui gives the triangle, crediting Jia Xian
17th centuryFrancePascal's treatise on the arithmetical triangle
1735–1741RussiaEuler's bridges paper is presented and published

Conclusion

Combinatorics has no single founder. Its counting rules grew out of poetry, arithmetic, and commentary in several cultures, and the arithmetic triangle appears in more than one tradition. Graph theory, by contrast, has a clear starting point in Euler's paper, though a full proof of his general rule for such walks came only in 1873 (Grötschel and Yuan 2012).

Key Terms

  • Combinatorics: The branch of mathematics that counts, arranges, and selects objects, often without listing every possibility.
  • Arithmetic triangle (Pascal's triangle): A triangle of numbers in which each entry is the sum of the two entries above it, and whose rows count the ways to choose items from a set.
  • Geometry of position: Euler's name for a kind of geometry concerned with where things are and how they're connected, rather than with measurement.
  • Graph theory: The study of networks made of points and the connections between them, where only which points are connected matters, not distances or shapes.

References

  • Euler, Leonhard. 1741. "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Imperialis Petropolitanae 8 (dated 1736). Eneström E53.
  • Grötschel, Martin, and Ya-xiang Yuan. 2012. "Euler, Mei-Ko Kwan, Königsberg, and a Chinese Postman." In Optimization Stories, Documenta Mathematica Extra Volume ISMP, 43–50. doi:10.4171/DMS/6/10.
  • Katz, Victor J. 2018. A History of Mathematics: An Introduction. 3rd ed., Classic Version. New York: Pearson.
    • Free: None
    • Publisher: Pearson
    • Free companion: O'Connor and Robertson 2003
  • Mahesh, K., Aditya Kolachana, and K. Ramasubramanian. 2021. "Combinatorial Techniques in Munīśvara's Nisṛṣṭārthadūtī." Indian Journal of History of Science 56: 171–181. doi:10.1007/s43539-021-00019-9.
  • Misra, Anuj. 2021. "Sanskrit Mathematics in the Language of Poetry." Lecture, Gresham College, October 20, 2021.
  • O'Connor, J. J., and E. F. Robertson. 1996a. "Blaise Pascal." MacTutor History of Mathematics Archive, University of St Andrews. Last updated December 1996.
  • O'Connor, J. J., and E. F. Robertson. 2000. "Bhaskara II." MacTutor History of Mathematics Archive, University of St Andrews. Last updated November 2000.
  • O'Connor, J. J., and E. F. Robertson. 2003. "Yang Hui." MacTutor History of Mathematics Archive, University of St Andrews. Last updated December 2003.

Reading 4 min Done

The Multiplication Principle, Permutations, and Combinations

Introduction

How many different outfits are in your closet? How many ways can a team line up for a photo? You can answer questions like these without writing out every case, using one rule and two refinements of it.

This reading covers the multiplication principle, permutations, combinations, and how the arithmetic triangle gives combination counts at a glance.

Choices in Stages

Suppose you own 3 shirts and 4 pairs of pants. Each shirt can go with any of the 4 pairs, so each shirt gives 4 outfits. Three shirts give 4 outfits each, or 12 in all.

That reasoning is the multiplication principle: if a choice is made in stages, the number of possible outcomes is the product of the number of options at each stage. Here the stages are "pick a shirt" (3 options) and "pick pants" (4 options), so the count is 3 \times 4 = 12. Add a stage of 2 pairs of shoes, and the count becomes 3 \times 4 \times 2 = 24.

The principle also explains the 16 rhythms that Indian scholars counted for a four-syllable meter (Misra 2021). Each syllable is light or heavy, a choice with 2 options, made four times. That gives 2 \times 2 \times 2 \times 2 = 16 patterns.

Arrangements Where Order Matters

Now put 4 different books on a shelf. Any of the 4 can go first. Once that's chosen, 3 remain for the second spot, then 2 for the third, and 1 for the last. The multiplication principle gives 4 \times 3 \times 2 \times 1 = 24 orders.

An arrangement like this, where order matters, is a permutation. Products of the form 4 \times 3 \times 2 \times 1 come up so often that they have a name and a symbol. The factorial of a whole number n, written n! and read "n factorial," is the product of all the whole numbers from 1 up to n. So 4! = 24 and 3! = 6. The Indian mathematician Bhaskara II gave this rule for counting the numbers you can form by rearranging a set of different digits (Mahesh et al. 2021).

Permutations grow fast. Ten books can stand in 10! = 3{,}628{,}800 orders. That growth is why counting beats listing.

Selections Where Order Doesn't Matter

Suppose you need to choose 2 people from a group of 5 to share a task. The multiplication principle gives 5 \times 4 = 20 ordered choices: 5 options for the first person, then 4 for the second. But "Ana, then Ben" and "Ben, then Ana" are the same pair. Every pair has been counted twice, once in each order. So the number of pairs is 20 \div 2 = 10.

A selection like this, where order doesn't matter, is a combination. The general method is the same: count the ordered choices, then divide by the number of orders each selection can appear in. For a group of 3 chosen from 5, there are 5 \times 4 \times 3 = 60 ordered choices, and each group of 3 appears in 3! = 6 orders, so there are 60 \div 6 = 10 groups.

The key question in any counting problem is whether order matters:

QuestionDoes order matter?Count
Gold, silver, and bronze among 5 runnersYes (permutation)5 \times 4 \times 3 = 60
A committee of 3 from 5 peopleNo (combination)60 \div 6 = 10
A first and a second speaker from 5 peopleYes (permutation)5 \times 4 = 20
A pair of partners from 5 peopleNo (combination)20 \div 2 = 10

Reading Combinations from the Triangle

The arithmetic triangle, also called Pascal's triangle, gives combination counts without any division. It starts with a 1 at the top. Each row begins and ends with 1, and every other entry is the sum of the two entries above it. Here are its first rows:

\begin{array}{c} 1 \\ 1 \quad 1 \\ 1 \quad 2 \quad 1 \\ 1 \quad 3 \quad 3 \quad 1 \\ 1 \quad 4 \quad 6 \quad 4 \quad 1 \\ 1 \quad 5 \quad 10 \quad 10 \quad 5 \quad 1 \end{array}

Number the rows from 0 at the top, and number the entries in each row from 0 on the left. Then entry k in row n is the number of ways to choose k items from n. Row 5 reads 1, 5, 10, 10, 5, 1, so there are 10 ways to choose 2 people from 5, matching the count by division. Row 4 reads 1, 4, 6, 4, 1: the number of four-syllable rhythms with 0, 1, 2, 3, or 4 heavy syllables. Those numbers add up to 16, the same total the multiplication principle gives.

Conclusion

Counting by stages turns questions about thousands or millions of cases into a short calculation. Most everyday counting problems come down to the multiplication principle plus one decision: whether order matters. The arithmetic triangle records the answers for combinations in a form that has been rediscovered in several cultures.

Key Terms

  • Multiplication principle: If a choice is made in stages, the number of possible outcomes is the product of the number of options at each stage.
  • Permutation: An arrangement of items in which order matters.
  • Factorial: The product of all the whole numbers from 1 up to a given whole number n, written n!.
  • Combination: A selection of items in which order doesn't matter.

References

Reading 4 min Done

The Pigeonhole Principle

Introduction

Some of the most useful facts in mathematics sound too plain to need saying. If ten letters go into nine mail slots, some slot gets at least two letters. That observation proves results that look surprising at first.

This reading covers the pigeonhole principle, how to find the number that guarantees an outcome, and why the principle proves that something exists without telling you where it is.

More Items Than Boxes

The pigeonhole principle says that if more items are placed into boxes than there are boxes, at least one box holds two or more items. The name comes from pigeons and the small compartments, or pigeonholes, they roost in. If 10 pigeons settle into 9 pigeonholes, at least one hole has two pigeons.

The reason is a short argument by contradiction. Suppose every box held at most one item. Then the number of items would be at most the number of boxes. That contradicts having more items than boxes, so some box must hold two or more.

A stronger version covers larger crowds. If more than twice as many items as boxes are placed, some box holds at least three. In general, if you place more than k times as many items as there are boxes, where k is any whole number, some box holds at least k + 1 items.

Finding the Number That Guarantees a Match

A drawer holds socks in three colors, and the room is dark. How many socks must you take to be sure of a matching pair? The boxes are the three colors, and each sock you draw goes into the box of its color.

To find the answer, look at the worst case. Three socks could all be different colors, one in each box, so three aren't enough. A fourth sock must land in a box that already has one. So 4 socks always give a matching pair, and 4 is the smallest number that does.

That smallest number is a guarantee: the least number of items that ensures an outcome however the items fall, found by considering the least favorable way they could fall. The method is always the same. Fill every box as fully as you can without producing the outcome, then add one. To be sure of three socks of one color, you could hold two of each color, or 6 socks, without succeeding, so 7 is the guarantee.

Birthdays work the same way. Counting February 29, there are 366 possible birthdays. In a group of 366 people, everyone could in principle have a different one. In any group of 367 people, at least two must share a birthday. No survey is needed, and no exception is possible.

Proving That Something Exists

The birthday argument has an unusual feature. It proves that two people in the group share a birthday, but it doesn't say which two, or which day. An existence proof is a proof that something must exist without identifying which one it is.

Existence proofs are common in combinatorics. Sometimes finding the example would mean checking a huge number of cases, while showing that one must exist takes a few lines. The pigeonhole principle is often the tool that makes this possible: it shows that a match, a repeat, or a pattern can't be avoided.

Patterns That Can't Be Avoided

A deeper version of the same idea is the starting point of Ramsey theory: the part of combinatorics showing that any large enough structure must contain an orderly pattern somewhere inside it, however it's arranged.

The best-known case concerns a party. Every pair of guests is either friends or strangers. Among any 6 guests, there are always 3 who are all friends with one another or 3 who are all strangers. The proof starts with the pigeonhole principle applied to one guest's five relationships.

For larger patterns, the exact group size needed is surprisingly hard to find. Mathematicians define a Ramsey number as the smallest group size that guarantees such a pattern, and they know only a few of these numbers exactly. A paper first posted in 2023 and published in 2026 gave the first exponential improvement on an upper limit for them that dates from 1935 (Campos et al. 2026).

Conclusion

The pigeonhole principle turns "more items than boxes" into a guarantee. Applying it means finding the right boxes and then the worst case. It can prove that a match or pattern exists while leaving open where it is, and in Ramsey theory that gap between existence and location is still the subject of research.

Key Terms

  • Pigeonhole principle: If more items are placed into boxes than there are boxes, at least one box holds two or more items.
  • Guarantee: The least number of items that ensures an outcome however the items fall, found by considering the least favorable way they could fall.
  • Existence proof: A proof that something must exist without identifying which one it is.
  • Ramsey theory: The part of combinatorics showing that any large enough structure must contain an orderly pattern somewhere inside it, however it's arranged.

References

  • Campos, Marcelo, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe. 2026. "An Exponential Improvement for Diagonal Ramsey." Annals of Mathematics 203 (3): 869–932. doi:10.4007/annals.2026.203.3.4. First posted as arXiv:2303.09521 (2023).

Reading 4 min Done

Graphs and Euler's Rule for Tracing Every Edge

Introduction

Can you draw a figure without lifting your pen and without going over any line twice? Children try this with envelopes and stars. Euler's answer to the Königsberg bridges puzzle settles it for every figure at once, by counting.

This reading covers graphs and their parts, why points where an odd number of lines meet decide the question, Euler's rule, and what Euler did and didn't prove. Citations to Euler's paper use the paragraph numbers (§) he gave it.

Dots, Lines, and Degree

A graph is a collection of points, called vertices, joined by lines, called edges, in which only which points are joined matters. Each point is a vertex (plural "vertices"): a point in a graph, standing for a place, a person, or any other object. Each line is an edge: a connection between two vertices. Two vertices may be joined by more than one edge, as two land areas can be joined by more than one bridge.

A graph records only which vertices are joined. It doesn't care how long the edges are, whether they're straight or curved, or where the vertices sit on the page. A street map, a family tree, and a diagram of computer connections can all be graphs.

The degree of a vertex is the number of edges that meet at it. In the Königsberg bridges graph, the island has degree 5 and the other three land areas have degree 3. A vertex with an odd degree is an odd vertex; one with an even degree is an even vertex.

Graphs here are networks, not the charts of data you may know from school.

Why Odd Vertices Matter

An Euler path is a route through a graph that uses every edge exactly once. You can revisit vertices as often as you like, but each edge is crossed once and only once.

Follow such a route and watch any vertex in the middle of it. Each time you pass through, you arrive along one edge and leave along another. Every pass uses two edges at that vertex. So if the route passes through a vertex several times and doesn't start or end there, the vertex's edges are used up in pairs, and its degree must be even.

Only the two ends of the route can break this pattern. Where you start, you leave once without having arrived. Where you finish, you arrive once without leaving. So at most two vertices can have odd degree: the start and the finish. If the route ends where it began, there are no odd vertices at all.

Euler's Rule

Put those observations together, and you get the rule. It applies to a connected graph, one in which you can get from any vertex to any other along edges.

Number of odd verticesCan every edge be traced exactly once?
0Yes, as a closed route that ends where it starts. You can start anywhere
2Yes, but only as a route that starts at one odd vertex and ends at the other
More than 2No

A graph can't have exactly one odd vertex. Each edge adds 1 to the degree of each of its two ends, so the degrees always add up to twice the number of edges, an even number. Odd vertices therefore come in pairs.

Euler stated the three cases in his paper (Euler 1741, §20). For Königsberg, four odd vertices meant no walk could cross every bridge once.

What Euler Proved, and What Came Later

The rule has two directions, and they weren't settled at the same time. The argument above shows that more than two odd vertices make a route impossible. That direction is what Euler proved.

The other direction says that with zero or two odd vertices, a route always exists. Euler stated it and sketched how to build such a route by setting aside pairs of edges and restoring them (Euler 1741, §21), but he didn't prove it. The first full proof came from Carl Hierholzer, who outlined it to friends before his death in 1871. It was reconstructed from memory and published in 1873 (Grötschel and Yuan 2012).

Conclusion

Euler's rule answers a question about routes by counting, with no searching. You find the degree of each vertex, count the odd ones, and read off the answer. That reduction made the Königsberg paper the starting point of graph theory, and the rule is still the first result taught in the subject.

Key Terms

  • Graph: A collection of points, called vertices, joined by lines, called edges, in which only which points are joined matters.
  • Vertex: A point in a graph, standing for a place, a person, or any other object.
  • Edge: A connection between two vertices in a graph.
  • Degree: The number of edges that meet at a vertex.
  • Euler path: A route through a graph that uses every edge exactly once.
  • Connected: Describes a graph in which you can get from any vertex to any other along edges.

References

  • Euler, Leonhard. 1741. "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Imperialis Petropolitanae 8 (dated 1736). Eneström E53.
  • Grötschel, Martin, and Ya-xiang Yuan. 2012. "Euler, Mei-Ko Kwan, Königsberg, and a Chinese Postman." In Optimization Stories, Documenta Mathematica Extra Volume ISMP, 43–50. doi:10.4171/DMS/6/10.

Guided Reading 7 min Done

Worked Example: Solving the Königsberg Bridges Problem

Introduction

The Königsberg bridges puzzle asks whether a walk can cross each of seven bridges exactly once. Trying routes never settles it. Counting does.

This worked example solves the puzzle with Euler's reasoning, in the later language of graphs, then asks what change would make the walk possible. Citations to Euler's paper use the paragraph numbers (§) he gave it.

The Problem

In the 18th century, Königsberg had four areas of land separated by a river: an island in the middle, a north bank, a south bank, and a piece of land to the east between two branches of the river. Seven bridges joined them:

BridgesBetween
2The island and the north bank
2The island and the south bank
1The island and the eastern land
1The north bank and the eastern land
1The south bank and the eastern land

The question is whether a walk can cross every bridge exactly once. The walk may start and end anywhere, and it may cross land freely. Two things are asked: a yes-or-no answer with a reason that covers every possible route, and, if the answer is no, the smallest change to the bridges that would make such a walk possible.

Figure: A sketch of 18th-century Königsberg showing the river, the island, the north and south banks, the eastern land, and the seven bridges, placed beside its graph: four dots labeled A (island), B (north bank), C (south bank), and D (eastern land), joined by seven lines, with each dot's degree written next to it (A: 5, B: 3, C: 3, D: 3). Alt text: A river map with an island and seven bridges beside a diagram of four labeled dots joined by seven lines, showing that the map reduces to the diagram.

Working It Through

Step 1: Replace each land area with a vertex and each bridge with an edge

A graph is a collection of points, called vertices, joined by lines, called edges. Make one vertex for each land area: A for the island, B for the north bank, C for the south bank, and D for the eastern land. Then draw one edge for each bridge, joining the two areas it connects. A and B get two edges, as do A and C. A and D get one edge, as do B and D, and C and D.

This step throws away the width of the river, the length of each bridge, and the shape of the banks. What's left is which land areas each bridge connects. Euler made the same move by recording a walk as a sequence of land-area letters, ignoring everything else (Euler 1741, §§4–7).

Step 2: Count the edges at each vertex

The degree of a vertex is the number of edges that meet there. Count them from the table:

  • A, the island: 2 + 2 + 1 = 5
  • B, the north bank: 2 (to A) + 1 (to D) = 3
  • C, the south bank: 2 (to A) + 1 (to D) = 3
  • D, the eastern land: 1 (to A) + 1 (to B) + 1 (to C) = 3

As a check, add the degrees: 5 + 3 + 3 + 3 = 14. Each edge has two ends and adds 1 to the degree of each, so the degrees should add up to twice the number of edges. Twice 7 is 14, so the count is consistent. Euler tabulated the same numbers: 5 for the island and 3 for each of the other areas (Euler 1741, §14).

Step 3: Note the odd vertices

A vertex with an odd degree is an odd vertex. Here every vertex is odd: 5, 3, 3, and 3. That makes four odd vertices.

Odd vertices matter because every time a walk passes through a land area, without starting or ending there, it arrives by one bridge and leaves by another. Each pass uses two bridges, so an area that's only passed through needs an even number of them.

Step 4: Apply Euler's rule

Euler's rule says that a connected graph, one in which every vertex can be reached from every other, can have every edge traced exactly once only if it has zero or two odd vertices. With two, the route must start at one odd vertex and end at the other. With more than two, no such route exists (Euler 1741, §20).

The reason for "more than two" follows from Step 3. Only the start and the finish of a walk can have an odd number of bridges. Every other area must be even. Königsberg has four odd areas, but a walk has only two ends. At least two odd areas would have to be passed through without being an end, and that's impossible.

Euler also gave a second check, by counting appearances. A walk across all 7 bridges, written as a sequence of land areas, has 8 entries: the starting area and then one area after each crossing. An area touching 5 bridges must appear 3 times in the sequence, and an area touching 3 bridges must appear 2 times. That requires 3 + 2 + 2 + 2 = 9 entries, but the walk has only 8 (Euler 1741). The two methods agree.

Step 5: Ask what change would make a walk possible

A walk becomes possible when the number of odd vertices drops to two. Adding or removing one bridge changes the degree of two vertices by 1 each. If both of those vertices are odd, both become even, and the four odd vertices become two.

Add an eighth bridge between the north bank (B) and the south bank (C). Now the degrees are A: 5, B: 4, C: 4, D: 3. Only A and D are odd. Euler's rule says a walk exists, starting at one of them and ending at the other.

One such walk, written as a sequence of land areas, is A, B, A, C, A, D, B, C, D. It makes eight crossings and uses each bridge once, including the new one.

Removing a bridge works too. Without the bridge between the island and the eastern land, the degrees are A: 4, B: 3, C: 3, D: 2, and a walk from the north bank to the south bank crosses the remaining six bridges once each: B, A, B, D, C, A, C.

Key Considerations

Distances, the shape of the river, and the positions of the bridges are irrelevant; only which areas each bridge connects matters. Two layouts that look nothing alike have the same answer if they have the same graph.

The common mistake is concluding from failed attempts that no route exists. A thousand failed routes prove nothing about the routes not yet tried. Euler's argument shows that every route must fail, for a reason that doesn't depend on which route you pick.

Step 4 uses the half of Euler's rule that Euler proved: more than two odd vertices rule out a route. The other half, that zero or two odd vertices guarantee a route, he stated but didn't prove; the first full proof is credited to Carl Hierholzer and was published in 1873 (Grötschel and Yuan 2012). Step 5 doesn't depend on that proof, because it exhibits a route directly. Euler wrote of land areas and bridges; "vertex," "edge," and "degree" are later vocabulary.

Summary

Counting bridges at each land area settles the Königsberg puzzle for every possible route, and shows which single change would make a walk possible.

Degrees: island (A) 5, north bank (B) 3, south bank (C) 3, eastern land (D) 3. All four vertices are odd, and the degrees add to 14, twice the 7 bridges.

Verdict: more than two odd vertices, so no walk crosses each bridge exactly once.

One-bridge change: add a bridge between the north and south banks. The degrees become 5, 4, 4, 3, leaving two odd vertices (A and D). A walk then exists from the island to the eastern land: A, B, A, C, A, D, B, C, D.

  1. The degree sum checks Step 2: it must equal twice the number of edges.
  2. The verdict rests on the half of Euler's rule that Euler proved.
  3. The written-out walk checks the one-bridge change.

References

  • Euler, Leonhard. 1741. "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Imperialis Petropolitanae 8 (dated 1736). Eneström E53.
  • Grötschel, Martin, and Ya-xiang Yuan. 2012. "Euler, Mei-Ko Kwan, Königsberg, and a Chinese Postman." In Optimization Stories, Documenta Mathematica Extra Volume ISMP, 43–50. doi:10.4171/DMS/6/10.

Guided Conversation 12 min Done

Trace a Network in Your Neighborhood

In this conversation you'll take a small network you know, such as paths in a park or the rooms and doors of a building, and turn it into dots and lines. You'll be coached rather than told: you count and decide first, then check. You'll leave knowing whether your network can be traced in one path, and with a counting result of your own.

You'll have this conversation with an AI assistant, using your own account. Choose a button to open a new chat with the prompt already filled in, then press send to start. If the chat opens empty, copy the prompt and paste it in.

Run this conversation in whichever assistant you already use:

Open in ClaudeOpen in ChatGPT
Claude desktop app

To use another LLM, simply copy and paste the prompt into its chat window.

Show the full prompt (it lists misreadings to watch for, so skip it if you would rather come to the conversation fresh) 
Guided Conversation: Trace a Network in Your Neighborhood (about 12 minutes)

Note to the learner: press send to start. Everything below is facilitator guidance for the AI. It lists misconceptions to watch for, so skip it if you'd rather come to the conversation fresh.

Please facilitate a coached problem session with me. I'm an adult who is comfortable with basic high-school algebra but may be rusty or uneasy with math, exploring what combinatorics and graph theory are and whether to study them further. I'm studying counting arrangements and tracing networks. Follow this guidance for the whole conversation.

GOAL
Help me decide whether a network I describe can be traced in one path, crossing every connection once, and count arrangements with the multiplication principle.

HOW TO RUN THE CONVERSATION
- Ask one question at a time, then wait for my reply. Keep each of your turns under about 120 words.
- Don't lecture. Explain a point only when I need it to continue, then return to my network.
- Be curious, collegial, and patient. Ask for my approach before any hint, then give one hint at a time, smallest first; don't solve the problem for me. Define terms briefly on first use. Welcome disagreement when I give a reason.
- Plain conversation only: don't search the web or create files or documents.
- Aim for about 12 minutes, with most of the time on topics 2 and 3. If my replies are brief, offer one concrete prompt, such as "call the places A, B, C and say which pairs are joined," and move on. If I seem uncertain, shorten the conversation to 5-7 minutes. Always reach the final topic.
- Start now. Open with one or two warm sentences: this is a conversation, not a quiz; careful counting matters more than speed or being right; I can ask you to clarify anything. Then ask me to describe a small network I know, such as paths in a park, rooms and doors, or stops on an errand route.

TOPICS, IN ORDER
1. My network. Ask me to name 4 to 7 places in it and say which pairs are joined, and by how many connections. If I can't think of one, offer a square park with a path around its edge and one path across it from corner to corner. Follow-up: ask whether path lengths or shapes will matter, and let me guess.
2. Dots and lines. Ask me to draw it as dots (vertices) for places and lines (edges) for connections, then count the degree of each dot: the number of lines meeting there. Ask me to check that the degrees add up to twice the number of lines; if not, hint that a line was counted at only one end. Follow-up: which dots have an odd degree?
3. Euler's rule. Ask what I think the odd dots have to do with tracing every line once. Hints, one at a time: each pass through a dot uses two lines there; only the start and finish can use an odd number. Then ask for my verdict and a check by tracing a route. If the verdict is no, ask what single added or removed connection would make it yes.
4. Closing. Ask me to pick three places in my network and count the orders I could visit them in, then say whether the count changes if only the choice of places matters, not the order. Help me state the result in one or two sentences I can take into a practice problem set.

CORRECT METHOD AND ANSWER
- Method: count each vertex's degree; check the degrees sum to twice the number of edges; count the odd vertices. In a connected network, every edge can be traced exactly once only with zero or two odd vertices. With zero, start anywhere and end where you began. With two, start at one odd vertex and end at the other. More than two: impossible. The number of odd vertices is always even.
- Fallback network: a square with one diagonal has two corners of degree 3 (the diagonal's ends) and two of degree 2. Yes: start at one end of the diagonal, go around the square, and finish along the diagonal.
- Fixing a no: add or remove one edge between two odd vertices; both become even.
- Closing count: three places can be visited in 3 x 2 x 1 = 6 orders (multiplication principle). If order doesn't matter, they form just 1 selection. Choosing 3 of n places in order gives n x (n-1) x (n-2); without order, divide by 6.
- Euler stated the full rule but proved only the impossibility half; the first full proof is credited to Carl Hierholzer, published in 1873.

MISCONCEPTIONS TO CORRECT GENTLY
When one appears, name the accurate version briefly, then return to my network.
- "If I can't find a route, there isn't one": failed attempts prove nothing; Euler's rule decides it.
- "Order always matters in counting": permutations count orders; combinations ignore order.
- "Graph theory is about charts": here a graph is a network of dots and lines.
- "Path lengths matter": only which places are connected matters.
- "The pigeonhole principle tells you where the match is": it guarantees a match without locating it.

LIMITS
- Write all math in plain notation, such as 3 x 2 x 1 = 6 or n x (n-1).
- Don't count degrees, give the verdict, or solve the closing count before I've attempted it.
- Don't introduce other graph topics beyond naming them if I ask.
- Don't say Euler invented graph theory or that combinatorics had a single founder.

TO FINISH
After my closing answer, close in one short turn:
- Affirm one specific thing I worked out, in my own words where possible.
- Suggest one or two next steps that fit how the conversation went. Possible steps: test Euler's rule on an envelope shape or a five-pointed star; add one connection to my network and predict the new verdict; recount the degrees with the doubling check.
- Restate my verdict and count on their own line, labeled "My network result," so I can copy it.

Problem Set 15 minOptional Done

Counting and Tracing

Overview

This optional problem set gives you practice with three tools: the multiplication principle for counting choices made in stages, the pigeonhole principle for guaranteeing a match, and Euler's rule for deciding whether a network can be traced in one path. The problems start with a direct count and build from there. All you need is basic arithmetic and a pencil.

Before each counting problem, decide whether order matters. For each network, count the degree of each vertex, that is, the number of lines meeting at each point. Then compare your answers with the worked solutions.

Problems

Problem 1

You have 3 shirts and 4 pairs of pants. How many different outfits of one shirt and one pair of pants can you make?

Once you've tried the problem, check your work against the solution.Show the solution to Problem 1Hide the solution

Answer: 12

Method:

  1. The choice happens in two stages: a shirt, then pants.
  2. There are 3 options at the first stage and 4 at the second.
  3. By the multiplication principle, multiply: 3 \times 4 = 12.

Most common error: adding instead of multiplying (3 + 4 = 7). Adding counts the clothes, not the outfits. Each shirt pairs with every pair of pants, so the counts multiply.

Problem 2

In how many different orders can 4 different books stand on a shelf?

Once you've tried the problem, check your work against the solution.Show the solution to Problem 2Hide the solution

Answer: 24

Method:

  1. Order matters, so this is a permutation.
  2. Any of the 4 books can go first, then any of the remaining 3, then 2, then 1.
  3. Multiply: 4 \times 3 \times 2 \times 1 = 24, which is 4! ("4 factorial").

Most common error: stopping at 4 \times 3 = 12 or writing 4 \times 4 = 16. Each spot has one fewer option than the spot before, because a book can't stand in two places at once.

Problem 3

How many different pairs of people can be chosen from a group of 5?

Once you've tried the problem, check your work against the solution.Show the solution to Problem 3Hide the solution

Answer: 10

Method:

  1. Order doesn't matter: the pair Ana and Ben is the same as Ben and Ana. So this is a combination.
  2. Count ordered choices first: 5 options for the first person, 4 for the second, giving 5 \times 4 = 20.
  3. Each pair was counted twice, once in each order, so divide by 2: 20 \div 2 = 10.
  4. Check: row 5 of the arithmetic triangle (Pascal's triangle) reads 1, 5, 10, 10, 5, 1, and the entry for choosing 2 is 10.

Most common error: answering 20. That counts ordered choices, as if "first and second" mattered.

Problem 4

A drawer holds socks of three colors, and the room is dark. How many socks must you take out to be sure of having a matching pair?

Once you've tried the problem, check your work against the solution.Show the solution to Problem 4Hide the solution

Answer: 4

Method:

  1. Treat the three colors as three boxes. Each sock you draw goes into the box of its color.
  2. Look at the worst case: 3 socks could be one of each color, with no match.
  3. The fourth sock must go into a box that already holds a sock, so 4 socks guarantee a pair.
  4. Three socks don't guarantee it, so 4 is the smallest number that does.

Most common error: answering 2 or 6. Two socks might match, but they aren't guaranteed to. Six is enough, but it isn't the smallest number that guarantees a pair.

Problem 5

Draw a square and one of its diagonals. Can you trace every line exactly once without lifting your pen? If yes, where must you start?

Once you've tried the problem, check your work against the solution.Show the solution to Problem 5Hide the solution

Answer: Yes. Start at one end of the diagonal and finish at the other.

Method:

  1. Label the corners. The two corners joined by the diagonal each have 3 lines meeting there (two sides and the diagonal). The other two corners each have 2.
  2. So there are exactly two odd vertices, the ends of the diagonal.
  3. By Euler's rule, a connected figure with exactly two odd vertices can be traced in one path that starts at one odd vertex and ends at the other.
  4. Check with a route: label the corners 1, 2, 3, 4 around the square, with the diagonal from 1 to 3. Trace 1 to 2, 2 to 3, 3 to 4, 4 to 1, then 1 to 3 along the diagonal. That uses all five lines once.

Most common error: starting at a corner with 2 lines. From there you'll always be left with a line you can't reach without retracing. The start and finish must be the odd corners.

Self-Check

Check that:

  • Each count uses the multiplication principle or a combination, and you decided first whether order matters
  • Your network answer names the odd vertices
  • Your pigeonhole answer is the smallest number that guarantees a match, not just a number that's large enough

Knowledge Check 10 min Done

Counting arrangements and the bridges of Königsberg

This ungraded knowledge check assesses your understanding of how combinatorics and graph theory answer "how many?" and "is it possible?" without listing every case. You'll be asked about the history of counting and networks, the multiplication principle and combinations, the pigeonhole principle, and Euler's rule for tracing every edge.

Note: Use this to test yourself, review the feedback on any questions you miss, and retry until you feel confident before moving forward.

5 questions · ungraded · retry as often as you like