The Seven Bridges of Konigsberg

Konigsberg is a town in former Prussia that is built around the Pregel River.  In the eighteenth century, there were seven bridges that connected different parts of the town that the townspeople enjoyed using for their evening strolls.  However, it seemed that no matter where they started or which way they went, the townspeople could not find a route that used all seven bridges exactly once.  Finding such a route became known as the as the Seven Bridges of Konigsberg Problem.

The Seven Bridges of Konigsberg Problem:

Find a walkable path that crosses each bridge exactly once.

In 1736, the Swiss mathematician Leonhard Euler proved that there was no route in Konigsberg that used all seven bridges exactly once.  He reinterpreted the problem by changing all the islands to points and all the bridges to line segments.  Euler then reasoned two things for a continuous (or walkable) path to exist in such a system:

1) Every point except for the starting and ending points must have an even number of line segments connected to it (because it would need n times to enter and n times to exit for a total of 2n). 

2) There can be at most two points that have an odd number of line segments connected to it – the starting and ending points.

In the Konigsberg problem, all four points have an odd number of line segments connected to it (the northern island is connected by 3 bridges, the western island is connected by 5 bridges, the eastern island is connected by 3 bridges, and the southern island is connected by 3 bridges), so a solution is impossible.

The Seven Bridges of Konigsberg Problem:

Reinterpreted as points and line segments.

The same reasoning can be used on problems where you must draw a figure without lifting your pencil, such as this picture of a house below:

The House Problem:

Draw this house without lifting your pencil.

Reinterpreting this house as points and line segments, like Euler did with the seven bridges of Konigsberg, shows the following:

The House Problem:

Reinterpreted as points and line segments.

The top point on the roof has 2 line segments connected to it, the bottom points of the roof have 4 line segments connected to it, the middle point inside the house has 4 line segments connected to it, and the bottom points of the house have 3 line segments connected to it.  Since all points have an even number of line segments connected to it except for the bottom two, we know that it is possible to draw this figure with a continuous line.  We also know that these bottom two points must be the starting and ending points since they are the only two points with an odd number of line segments connected to them.  Now that we know the trick of finding the starting and ending points, discovering a way to draw this picture with one continuous line becomes much easier.  One solution is as follows:

The House Problem:

One solution.

but there are many other solutions as well.

My son and I recently built an arcade machine where these theorems came in handy.  We wanted to place some lights around some of the edges of the arcade, and to keep it simple, we wanted to use just one continuous string of lights. 

We originally wanted to place a border around the top marquee sign, a border around the playing area, and another border around the keyboard drawer.  However, no matter how many times we tried, we couldn’t do it.  Reinterpreting this as a system of points and line segments showed us why:

Since there were more than two points with an odd number of line segments connected to it, it was impossible to place a continuous string of lights in this way.  So we revised the design so that there was a border around just the sign and the playing area, and not around the keyboard drawer, like this:

Now all but two points have an even number of line segments, making it possible for us to place a continuous string of lights in the way described.  We also knew that the middle two points (under the sign but above the playing area) with the odd number of line segments connected to them had to be the starting and ending points.  Therefore, one way to place a continuous string of lights as pictured would be as follows:

which is exactly how we did it.

The Seven Bridges of Konigsberg Problem started out as a simple challenge between some townspeople who enjoyed going on evening strolls.  Euler reinterpreted the problem as a diagram of points and lines, and discovered some basic theorems that are foundational to a branch of mathematics called graph theory.  These theorems have several applications, including how to solve puzzles in which you must draw a certain picture without lifting your pencil, drawing workable electrical diagrams, and much, much more.  It is truly amazing how versatile these simple theorems are.

Pick’s Theorem

Pick’s Theorem, first described by the Jewish-Austrian mathematician Georg Alexander Pick in 1899, finds the area of any polygon formed on a unit-based grid of points.  It states that

                                                                                                                                  

A = ½b + i – 1

where b is the number of points on the border of the polygon, and i is the number of points in the interior of the polygon.

Here are a few examples of Pick’s Theorem applied to some polygons:

Pick’s Theorem Examples
b = 12 i = 4 A = ½b + i – 1 A = ½·12 + 4 – 1 = 9	b = 9 i = 1 A = ½b + i – 1 A = ½·9 + 1 – 1 = 4½	b = 10 i = 2 A = ½b + i – 1 A = ½·10 + 2 – 1 = 6

These three examples can all be verified by common area formulas.  The first example, the square, has an area of A = s², so A = 3² = 9.  The second example, the triangle, has an area of A = ½bh, so A = ½·3·3 = 4½.  The last example, the house-shaped polygon, is made up of 5 unit squares for the bottom and 2 half unit squares for the roof, so A = 5(1) + 2(½) = 6.  Pick’s Theorem was able to correctly calculate the area of each of these shapes.

Restrictions

Amazingly, Pick’s Theorem works for any polygon as long as the following restrictions are met:

1)  All vertices must be on one of the unit grid points.

2)   All border points must connect to exactly two segments.

3)  There are no holes.

4)  There are no curved edges.

All of these restrictions, except for the first, are derived by the very definition of a polygon itself.

Pick’s Theorem Restrictions
All vertices must be on  one of unit grid points.	All border points must connect to two segments.
No holes.	No curves.

Proof

The proof for Pick’s Theorem is quite involved.  The first step is to show that Pick’s Theorem is true for any triangle using variable coordinates.  The second step is to show that combining a triangle with another triangle (or another polygon in which Pick’s Theorem is already true) preserves Pick’s Theorem.  Since any polygon with more than three sides can be subdivided into triangles, this shows that Pick’s Theorem is true for any polygon as well.  The complete proof can be found here.

                                                                                           

Variation of Pick’s Theorem – Triangular Grid

                 

There are several variations to Pick’s Theorem that are also worth mentioning, and the first variation is to use a triangular grid of points instead of a square grid of points.  Surprisingly, the formula for Pick’s Theorem remains nearly the same for a triangular grid of points except that it is multiplied by a factor of ^√3/₂, the height of an equilateral triangle for a unit triangle.  Therefore, Pick’s Theorem for the area of any polygon formed on a unit-based grid of triangular points is

                                                                                                                                  

A = ^√3/₂(½b + i – 1)

                                     

where b is the number of points on the border of the polygon, and i is the number of points in the interior of the polygon.

This variation of Pick’s Theorem for a triangular grid can be demonstrated through a series of transformations that changes a square unit grid to a triangular unit grid.  The first step is to start off with a square unit grid and skew each row of points half a unit to the right (or left).  Since skewing a shape preserves area (for example, a rectangle and a parallelogram both have an area of A = bh), the area formula remains as A = ½b + i – 1.  The second step is to shrink the height between rows by a factor of ^√3/₂, the height of an equilateral triangle for a unit triangle.  This new transformation changes the area by its shrinking factor, namely ^√3/₂, so the new formula becomes A = ^√3/₂(½b + i – 1).

Transforming a Square Unit Grid to a Triangular Unit Grid
Start with a square unit grid	Skew each row of points half a unit to the right	Shrink the ht. between rows by a factor of √3/2

If both the height and the width are shrunk so that each triangle has a unit area (instead of each side having a unit area), then the formula for Pick’s Theorem is multiplied by a factor of 2 (the area of each parallelogram formed by two adjacent unit triangles).  In this variation, Pick’s Theorem would be A = 2(½b + i – 1), or

A = b + 2i – 2

where once again b is the number of points on the border of the polygon, and i is the number of points in the interior of the polygon.

Here are some examples of this variation of Pick’s Theorem for a triangular grid in which each triangle has a unit area:

Variation of Pick’s Theorem – Triangular Grid
b = 12 i = 3 A = b + 2i – 2 A = 12 + 2·3 – 2 = 16	b = 12 i = 1 A = b + 2i – 2 A = 12 + 2·1 – 2 = 12

These two examples can be verified by counting the number of unit triangles inside each shape.  The first example, the large triangle, is made up of 16 unit triangles, so it has an area of 16.  The second example, the star, is made up of 12 unit triangles, so it has an area of 12.  This variation of Pick’s Theorem for a triangular grid was able to correctly calculate the area of each of these shapes.

More information on this variation of Pick’s Theorem for a triangular grid can be found at http://www.drking.org.uk/hexagons/pick/index.html.

Variation of Pick’s Theorem – Shapes with Holes

Although one of the restrictions for using the regular version of Pick’s Theorem is that there cannot be any holes in the polygon, this restriction can be lifted by using the adjusted equation

A = ½b + i + h – 1

where b is the number of border points, i is the number of interior points, and h is the number of holes.

Recall that the proof for the regular version of Pick’s Theorem makes use of the fact that any polygon can be built by adding one triangle at a time on a shared side and still preserve Pick’s Theorem.  However, when building a shape with a hole in it, there must be a quadrilateral added in the process that acts as a bridge with two shared sides instead of one, which will result in a contradiction of Pick’s Theorem.  The discrepancy can be accounted for by adding the number of holes in the shape.

For example, in the picture above, the dark gray square is bridging the gap on the light gray polygon to form one hole.  According to Pick’s Theorem, the two areas are are A = ½b₁ + i₁ – 1 and A = ½b₂ + i₂ – 1 for a combined area of A = ½(b₁ + b₂) + i₁ + i₂ – 2, where b₁ and i₁ are the number of border and interior points on the dark gray square, b₂ and i₂ are the number of border and interior points on the light gray polygon.  Letting s₁ and s₂ be the number of border points on the two shared sides (including the endpoints), the resulting shape has the same number of border and interior points as the original two polygons except that 2(s₁ – 2) border points change to s₁ – 2 interior points, the two endpoints of s₁ are repeated, 2(s₂ – 2) border points change to s₂ – 2 interior points, and the two endpoints of s₂ are repeated.  So the area of the resulting shape in terms of Pick’s Theorem is:

= ½(b₁ + b₂ – 2(s₁ – 2) – 2 – 2(s₂ – 2) – 2) + (i₁ + i₂ + (s₁ – 2) + (s₂ – 2)) – 1

= ½b₁ + ½b₂ – (s₁ – 2) – 1 – (s₂ – 2) – 1 + i₁ + i₂ + (s₁ – 2) + (s₂ – 2) – 1

= ½b₁ + ½b₂ – (s₁ – 2) – 1 – (s₂ – 2) – 1 + i₁ + i₂ + (s₁ – 2) + (s₂ – 2) – 1

= ½(b₁ + b₂) + i₁ + i₂ – 3

= (½b₁ + i₁ – 1) + (½b₂ + i₂ – 1) – 1

= (area of the dark gray square) + (area of the light gray polygon) – 1

For every hole that is created, and extra 1 is subtracted, so the equation can be balanced by adding the number of holes in the shape.

Here are some examples of this variation of Pick’s Theorem for shapes with holes:

Variation of Pick’s Theorem – Shapes with Holes
b = 32 i = 16 h = 1 A = ½b + i + h – 1 A = ½·32 + 16 + 1 – 1 = 32	b = 40 i = 8 h = 5 A = ½b + i + h – 1 A = ½·40 + 8 + 5 – 1 = 32

These two examples can be verified by common area formulas.  The first example, the square with a smaller square taken out, has an area of A = 6² – 2² = 36 – 4 = 32.  The second example, the square with four triangles and a diamond taken out, has an area of A = 6² – 4·½·1·1 – ½·2·2 = 36 – 2 – 2 = 32.  This variation of Pick’s Theorem for shapes with holes was also able to correctly calculate the area of both of these shapes.

More information on this variation of Pick’s Theorem for shapes with holes can be found at http://jwilson.coe.uga.edu/emat6680fa05/schultz/6690/pick/pick_main.htm.

Variation of Pick’s Theorem – Three Dimensions

There are many mathematicians who believe that all attempts to extrapolate Pick’s Theorem to the third dimension result in failure.  Indeed, the volume of a polyhedron formed by points on a three-dimensional unit grid cannot be determined by the number of its interior points and border points.  One quick counterexample is to compare the smallest triangular prism that can be formed on a unit grid and the smallest octahedron that can be formed on a unit grid. 

Both polyhedrons have the same number of interior and border points (0 interior points and 6 border points), but their volumes are different (the triangular prism has a volume of ½ and the octahedron has a volume of ²/₃).

However, if all the restrictions to Pick’s Theorem are bumped up a dimension as well, it is possible to derive a variation of Pick’s Theorem for finding volumes in the third dimension.  The new restrictions are as follows:

1)  All sides must be on one of the unit grid segments.

2)  All border sides must connect to exactly two faces.

3)  There are no topological holes or hollow parts.

4)  There are no curved faces.

These new restrictions force all eligible polyhedrons to be blocky, which admittedly is not as elegant as the two dimensional version of Pick’s Theorem, but if these new restrictions are met, the volume of a polyhedron can be determined by

V = ⅛(b_e + 4i_e – 4i_p – 4)

where b_e is the number of edges on the border of the polyhedron, i_e is the number of edges on the interior of the polyhedron, and i_p is the number of points on the interior of the polyhedron.

Here are some examples of this variation of Pick’s Theorem for three dimensions:

Variation of Pick’s Theorem – Three Dimensions
be = 48, ie = 6, ip = 1 V = ⅛(be + 4ie – 4ip – 4) V = ⅛(48 + 4·6 – 4·1 – 4) = 8	be = 108, ie = 36, ip = 8 V = ⅛(be + 4ie – 4ip – 4) V = ⅛(108 + 4·36 – 4·8 – 4) = 27
be = 44, ie = 2, ip = 0 V = ⅛(be + 4ie – 4ip – 4) V = ⅛(44 + 4·2 – 4·0 – 4) = 6	be = 60, ie = 0, ip = 0 V = ⅛(be + 4ie – 4ip – 4) V = ⅛(60 + 4·0 – 4·0 – 4) = 7

These examples can be verified by counting the number of unit blocks inside each shape.  The first example, the 2 x 2 x 2 cube, is made up of 8 unit blocks, so it has a volume of 8.  The second example, the 3 x 3 x 3 cube, is made up of 27 unit blocks, so it has a volume of 27.  The third example, the staircase, is made up of 6 unit blocks, so it has a volume of 6.  Finally, the last example, the letter H, is made up of 7 unit blocks, so it has a volume of 7.  This variation of Pick’s Theorem for three dimensions was also able to correctly calculate the volume of each of these shapes.

The proof for this variation of Pick’s Theorem for three dimensions is also quite long and involved, and can be found here.

Conclusion

Pick’s Theorem is not a very well-known theorem other than to a few math trivia buffs.  It does not appear in many Geometry textbooks, nor is it taught in many Geometry classes, and yet it is easy to understand (since it is based on a unit grid), flexible (there are many variations), and useful (it can be used to find areas and volumes).  For these reasons, Pick’s Theorem is one of the most beautiful and elegant theorems in mathematics.

Proof of Pick’s Theorem for Three Dimensions

If a polyhedron is formed on a unit grid such that all of its sides are on one of the unit grid segments, all of its border sides connect to exactly two faces, there are no topological holes or hollow parts, and there are no curved faces, then the volume of that polyhedron can be determined by

V = ⅛(b_e + 4i_e – 4i_p – 4)

where b_e is the number of edges on the border of the polyhedron, i_e is the number of edges on the interior of the polyhedron, and i_p is the number of points on the interior of the polyhedron.

Since the first restriction is that all sides are on one of the unit grid segments, this means that all eligible polyhedrons must be made out of unit blocks.  So to prove this variation of Pick’s Theorem for three dimensions, the first step is to show that it is true for a single block, and the second step is to show that combining a unit block to another eligible polyhedron made up of unit blocks preserves this theorem.

                                            

The first step is to show that this variation of Pick’s Theorem for three dimensions is true for a single block.  This can be verified easily enough.  A single block has 12 border edges, 0 interior edges, 0 interior points, and 0 holes.  Therefore, using the formula we can calculate its volume to be V = ⅛(b_e + 4i_e – 4i_p + 4h – 4) = ⅛(12 + 4·0 – 4·0 + 4·0 – 4) = 1, which is exactly the volume we would expect.

The second step is to show that combining a unit block to another eligible polyhedron made up of unit blocks preserves this variation of Pick’s Theorem.  Depending on the already existing polyhedron, the unit block can be combined so that it shares 1 face, 2 faces (adjacently), 3 faces (adjacently in a corner or adjacently in a row), 4 faces (adjacently in a corner), or 5 faces.  As the table below shows, all of these combinations keep the equation to the theorem balanced:

1 shared face	8 new border edges: beN = beO + 8 0 new interior edges: ieN = ieO 0 new interior points: ipN = ipO volume increases by 1: VN = VO  + 1	VO = ⅛(beO+4ieO–4ipO–4) VO+1 = ⅛(beO+4ieO–4ipO–4)+1 VO+1 = ⅛(beO+4ieO–4ipO–4+8) (VO+1) = ⅛((beO+8)+4ieO–4ipO–4) VN = ⅛(beN+4ieN–4ipN–4)
2 shared  adjacent faces	5 – 1 = 4 new border edges: beN = beO + 4 1 new interior edge: ieN = ieO + 1 0 new interior points: ipN = ipO volume increases by 1: VN = VO  + 1	VO = ⅛(beO+4ieO–4ipO–4) VO+1 = ⅛(beO+4ieO–4ipO–4)+1 VO+1 = ⅛(beO+4ieO–4ipO–4+8) VO+1 = ⅛(beO+4ieO–4ipO–4+4+4) VO+1 = ⅛(beO+4+4ieO+4–4ipO–4) VO+1 = ⅛((beO+4)+4(ieO+1)–4ipO–4) VN = ⅛(beN+4ieN–4ipN–4)
3 shared adjacent faces in a corner	3 – 3 = 0 new border edges: beN = beO 3 new interior edges: ieN = ieO + 3 1 new interior point: ipN = ipO + 1 volume increases by 1: VN = VO  + 1	VO = ⅛(beO+4ieO–4ipO–4) VO+1 = ⅛(beO+4ieO–4ipO–4)+1 VO+1 = ⅛(beO+4ieO–4ipO–4+8) VO+1 = ⅛(beO+4ieO–4ipO–4+12–4) VO+1 = ⅛(beO+4ieO+12–4ipO–4–4) VO+1 = ⅛(beO+4(ieO+3)–4(ipO+1)–4) VN = ⅛(beN+4ieN–4ipN–4)
3 shared  adjacent faces in a row	2 – 2 = 0 new border edges: beN = beO 2 new interior edges: ieN = ieO + 2 0 new interior points: ipN = ipO volume increases by 1: VN = VO  + 1	VO = ⅛(beO+4ieO–4ipO–4) VO+1 = ⅛(beO+4ieO–4ipO–4)+1 VO+1 = ⅛(beO+4ieO–4ipO–4+8) VO+1 = ⅛(be+4ieO+8–4ipO–4) VO+1 = ⅛(beO+4+4(ieO+2)–4ipO+4(hO+1)–4) VN = ⅛(beN+4ieN–4ipN–4)
4 shared  adjacent faces in a corner	1 – 5 = 4 less border edges: beN = beO – 4 5 new interior edges: ieN = ieO + 5 2 new interior points: ipN = ipO + 2 volume increases by 1: VN = VO  + 1	VO = ⅛(beO+4ieO–4ipO–4) VO+1 = ⅛(beO+4ieO–4ipO–4)+1 VO+1 = ⅛(beO+4ieO–4ipO–4+8) VO+1 = ⅛(beO+4ieO–4ipO–4–4+20–8) VO+1 = ⅛(beO–4+4ieO+20–4ipO–8–4) VO+1 = ⅛(beO–4+4(ieO+5)–4(ipO+2)–4) VN = ⅛(beN+4ieN–4ipN–4)
5 shared faces	8 less border edges: beN = beO – 8 8 new interior edges: ieN = ieO + 8 4 new interior points: ipN = ipO + 4 volume increases by 1: VN = VO  + 1	VO = ⅛(beO+4ieO–4ipO–4) VO+1 = ⅛(beO+4ieO–4ipO–4)+1 VO+1 = ⅛(beO+4ieO–4ipO–4+8) VO+1 = ⅛(beO+4ieO–4ipO–4–8+32–16) VO+1 = ⅛(beO–8+4ieO+32–4ipO–16–4) VO+1 = ⅛(beO–8+4(ieO+8)–4(ipO–4)–4) VN = ⅛(beN+4ieN–4ipN–4)

Note: the following combinations are disregarded since holes or hollowed parts are restricted: 2 opposite faces (because a hole would be formed), 4 adjacent faces in a row (because it would start with a hole), and 6 faces (because it would start with a hollow part).

Since we have shown that this variation of Pick’s Theorem for three dimensions is true for a unit block, and have shown that this variation of Pick’s Theorem is preserved for combining a unit block to another eligible polyhedron made up of unit blocks, this variation of Pick’s Theorem must be true for all polyhedrons as well.