What's the area of this weird shape?

Turns out there's a really easy way to compute it.

6 00:00:17,540 --> 00:00:19,369 At the end of the last episode, I asked you to share one of your favorite proofs that uses the mathematical tools we explored-- bijections, pictures, induction, and more.

This week I figured I'd share one of mine.

To find the area of this shape it might seem like you have to do a bunch of trigonometry and do lots and lots of computations, but there's actually a simple formula for the area of this shape given by Pick's Theorem, and the proof of that formula is quite elegant, but to get there, we have to start somewhere entirely different by computing the Euler characteristic of a planar graph.

Let's find out what that means.

Let's say you have a graph, which is just a bunch of vertices connected by edges.

Then the Euler characteristic of the graph is defined to be the number of vertices minus the number of edges plus the number of faces.

The faces of a graph are just the spaces between the edges-- plus the entire region outside the graph counts as one face.

So this graph has 5 vertices, 6 edges, and 3 faces.

That makes its Euler characteristic 5 minus 6 plus 3, which is 2.

What about this graph?

It has 10 vertices, 11 edges, and 3 faces.

So the Euler characteristic is 10 minus 11 plus 3, which is, again, 2.

It's no coincidence that they both have Euler characteristic 2.

In fact, any planar graph, which means that you can draw the graph on a piece of paper without having the edges cross over each other, will have Euler characteristic 2.

Right now we'll prove that fact.

It'll help us later with Pick's Theorem.

David Eppsteins' web site, linked in the description, contains an impressive 20 different proofs using all kinds of different mathematical tools of the fact that a planar graph has Euler characteristic 2.

Here's my favorite-- induction on the number of vertices.

Remember from last episode that to prove something by induction, we first show that the formula for Euler's characteristic is true when there is only 1 vertex.

Then we show that, if it holds for a graph with N vertices, it holds for a graph with N plus 1 vertices.

Assume the graph only has 1 vertex.

Then it must look something like this.

All the edges are loops.

Each edge creates a new face, and there's an outside face.

So E plus 1 equals F, which rearranges to 1 minus E plus equals 2, which is the Euler characteristic formula for V equals 1.

Now, assume we know the Euler characteristic formula holds for a graph with N vertices.

Now we want to show it's true for a graph with N plus 1 vertices.

For your graph with N plus 1 vertices, pick an edge and contract it.

This means that you delete the edge, and you merge the two vertices at the end.

After contracting an edge, our graph has N vertices.

So we know that the Euler characteristic is 2.

When we contracted the edge, we removed one vertex and one edge, so the Euler characteristic didn't change.

It must have also been 2.

This proves by induction that all planar graphs have Euler characteristic 2.

Now, how is the Euler characteristic of a planar graph going to help us find the area of some crazy looking polygon?

Let's set up the problem more precisely.

Let's say we have a grid of dots spaced 1 centimeter apart.

It's called a two dimensional integer lattice.

Form a polygon which is just a shape with straight sides so that its corners, or vertices, are points on the integer lattice like this or this.

Let i be the number of points inside the polygon, and let b be the number of points on the boundary of the polygon.

So for this rectangle, i equals 8 and b equals 16, while for this shape, i equals 5 and b equals 5.

Remember at the beginning of this episode I said that we have an easy formula for the area of this crazy shape.

Here it is.

Pick's Theorem says that the area of a polygon whose vertices are on the integer lattice is given by the formula area equals i plus b over 2 minus 1.

You could pause here to verify it on some shapes that are easy to find the area of, like the rectangle, or try to prove it yourself.

Now, what's the proof of Pick's Theorem.

In other words, how do we show that the area is i plus b divided by 2 minus 1.

We'll break this down into three steps.

Step one-- show that any small triangle has area 1/2.

Step two-- break down our polygon into a bunch of small triangles.

Step three-- count the number of small triangles.

So for example, since we could break our rectangle into 30 small triangles and each has area 1/2, the rectangle has area 15.

Step one is to prove a lemma.

A lemma is kind of like a mini fact that helps you prove a bigger fact known as the theorem.

The lemma we want to prove is that small triangles have area 1/2.

To be specific, by small triangle, I mean one that doesn't contain any lattice points besides the three main vertices either on its interior or on the boundary, like this or this.

For the simplest small triangle, the right triangle, it's easy to see that it has area 1/2, but it's not just the right triangles.

Even the stretched out looking small triangles have area 1/2.

I'll leave it as a challenge problem for you to prove it.

Step two-- triangulate your polygon, which means break it into a bunch of small triangles.

It's always possible to do this.

We know from step one that each has area 1/2.

To find the total area, we just need to find out how many small triangles there are and multiply by 1/2.

Step three is to determine the number of small triangles.

How do we do it?

With Euler's formula.

Once we've triangulated our polygon, it looks like this, which is exactly the kind of graph with Euler characteristic 2.

Remember that the area outside of the graph counts as one big face, so the number of triangles in the graph is 1 less than the number of faces, so it's f minus 1.

Now, let's do a little computation using a few of our favorite math tools, including citing previous results, the Euler characteristic, and good old algebra.

The first step is to observe that 3 times f minus 1 plus the number of edges on the boundary is equal to 2e.

Why?

Look at the left side.

3 times f minus 1 is counting edges.

Each of the f minus 1 triangles has three edges.

The edges on the interior are counted twice since they are the sides of two different triangles, but the edges on the boundary are only counted once.

So when we add the number of edges on the boundary, we get twice the total number of edges.

Now, let's do some algebra to rearrange it like this.

We subtract 2f from each side, move the number or boundary edges and the 3 over, and factor the 2 out.

We like this formulation because it allows us to apply the formula for the Euler characteristic.

e minus f is equal to v minus 2, giving us this.

Now, notice that v, the number of vertices, is the sum of the number of vertices inside the polygon, which we called the variable i, and the number of vertices on the boundary of the polygon, which we called the variable b.

So v equals i plus b.

And the number of edges on the boundary is equal to b, the number of vertices on the boundary.

We plug these into our equation and do some algebraic rearranging to get this.

We distribute the two, rearrange the terms, and then subtract 1 from both sides.

Now we know how many small triangles there are.

2i plus b minus 2.

Step one-- showed us that each small triangle has area 1/2, so the area of the entire polygon is the number of small triangles it's broken into-- 2i plus b minus 2-- times the area of each small triangle-- 1/2.

That gives us i plus b divided by 2 minus 1, which proves Pick's Theorem.

Now, let's go back to the original shape-- this one.

There are 14 interior vertices and 25 vertices on the boundary.

So i equals 14, and b equals 25.

Plugging this into Pick's Theorem, the area is 25 and 1/2.

Easy.

I saw this proof of Pick's Theorem in "Proofs from The Book."

The title references mathematician Paul Erdos' talk about the book that God maintains of perfect proofs.

If you want to learn some of the most elegant and classic proofs in mathematics, I highly recommend you check out "Proofs from The Book."

ke d anifd ytioutl cesan.

p rove that something is unprovable.

Although that sounds like a contradiction, basically, yes.

You can prove that something is neither provable nor disprovable within a given axiom system.

It's called independent.

In the episode "Hierarchy of Infinities," we discussed the Continuum Hypothesis, which is independent of ZFC.

The proof that it's independent is tricky-- really tricky-- but it exists.

MKD asks something related, but different.

Is there an instance of a proposed new theorem which was still studied, even though nobody can prove it?

Well, axioms are neither proved nor disproved.

They're just taken as given, but there are some other math facts that are still studied despite not having been proven.

We don't call them theorems.

That label requires a proof, but for example, the Riemann Hypothesis is a very well studied unproven conjecture.

Finally, sleepyguy asked, how does her hair not have green screen in it?

Easy.

We don't shoot in front of a green screen.

We shoot in front of an endless hallway.