Become a Creator today!Start creating today - Share your story with the world!
Start for free
00:00:00
00:00:01
61: Look at this Graph! (Graph Theory)
833 Plays3 years ago
In mathematics, nature is a constant driving inspiration; mathematicians are part of nature, so this is natural. A huge part of nature is the idea of things like networks. These are represented by mathematical objects called 'graphs'. Graphs allow us to describe a huge variety of things, such as: the food chain, lineage, plumbing networks, electrical grids, and even friendships. So where did this concept come from? What tools can we use to analyze graphs? And how can you use graph theory to minimize highway tolls? All of this and more on this episode of Breaking Math.
Episode distributed under an Creative Commons Attribution-ShareAlike-NonCommercial 4.0 International License. For more information, visit CreativeCommons.org
[Featuring: Sofía Baca, Meryl Flaherty]
---
This episode is sponsored by
· Anchor: The easiest way to make a podcast. https://anchor.fm/app
Support this podcast: https://anchor.fm/breakingmathpodcast/support
Recommended
Transcript
Introduction to Graphs and Their Natural Inspiration
00:00:00
Speaker
In mathematics, nature is a constant driving inspiration. Mathematicians are part of nature, so this is natural. A huge part of nature is the idea of networks. These are represented by mathematical objects called graphs. Graphs allow us to describe a huge variety of things, such as the food chain, lineage, plumbing networks, electrical grids, and even friendships. So where did this concept come from? What tools can we use to analyze graphs?
00:00:25
Speaker
And how can you use graph theory to minimize highway tolls? All of this and more on this episode of Breaking Math.
Meet the Hosts and Episode Overview
00:00:32
Speaker
Episode 61, look at this graph.
00:00:44
Speaker
I'm Sophia. And I'm Meryl. And you're listening to Breaking Math. Today we've got a fun episode for you, but as always we're going to start with plugs for the show.
Promotions and Support Information
00:00:52
Speaker
So, tensors are the mathematical objects we use in Einstein's General Theory of Relativity. And now they're in poster form. We have a 24 by 36 inch poster that we made about tensors and it's available on Facebook.com such as Breaking Math Podcast. Just click on shop. They're matte, full color, and make a perfect addition to any office.
00:01:08
Speaker
So for $15.15 plus $4.50, a total of $19.65, you can get this poster for you or someone you know. So check it out at Facebook.com slash Breaking Math Podcast. Click on the store and see if it's right for you.
00:01:21
Speaker
We're on Patreon at patreon.com slash breakingmath. You can go there if you want to support the show. Even a $1 donation makes a huge difference and will send you a thank you message. With $1 or more, you can gain access to episodes slightly early and without ads. We also include the outlines we use to produce the show. We really appreciate your patronage at patreon.com slash breakingmath. For news about the show, we're on Twitter at breakingmathpod at facebook.com slash breakingmathpodcast. And we have an interactive website at breakingmathpodcast.app.
00:01:50
Speaker
Get in touch with us at breakingmathpodcast.gmail.com with questions, comments, suggestions, corrections and anything else.
Understanding Graphs: Vertices and Edges
00:02:09
Speaker
So a graph in its most basic definition is a set of vertices, which we can also call nodes, and a set of edges that connect these vertices together. So these nodes can be people and the edges can be friendships. Basically, it's a way to represent different types of networks, right?
00:02:29
Speaker
Yeah, another example is let's say that nodes are cities, the edges could be roads connecting these cities. So stay tuned for the rest of this episode. We're going to be talking about some fun stuff. We're going to be talking about some graph definitions, properties, some algorithms. And at the end, we're going to talk about how graphs can be applied to cartography in a weird way.
00:02:50
Speaker
All right, so graphs, we already talked about what they are, right? But want to go over it again, like mathematically. So a graph is denoted in parentheses V comma E, where V is the set of vertices and E is the set of edges.
00:03:04
Speaker
And what that means if something's denoted like V comma E inside a parentheses or something like that, it just means that we have different parts of this mathematical object, right? We have the vertices and we have the edges. They're kind of like different types of objects. It just means that they're put together and that they're not exactly the same thing. So the paths between the vertices, right, are called edges.
00:03:23
Speaker
That's right. So like an edge, let's say that we have a graph with vertices, we'll say A, B and C, something really simple like that. And let's say that A and B are connected. Then we say that there's an edge between A and B. So how does this relate to graphing a line or graphing like a quadratic equation? Yeah, so it really doesn't. They might share the same name, but they really do mean different things.
00:03:50
Speaker
Yeah, it's very, I mean, they both basically just mean writing. So it's about as vague as a name you can get without calling it entropy. So yeah, so as we said, yeah, the edges connect two vertices together and each edge can actually be denoted as two separate vertices,
Euler's Bridges of Königsberg and Graph Theory Origins
00:04:05
Speaker
right? So what is the history of this? Like every, like everything in math, it comes back to Euler. Leonid Euler lived in the 18th century. He knew about this problem called the seven bridges of Königsberg.
00:04:18
Speaker
So basically, do you want to give a description of what these bridges look like? Yeah, so what we have is an island and a peninsula defined by a canal that splits with two bridges on either side of the island and a bridge going from the island to the peninsula. So we have seven bridges in total.
00:04:35
Speaker
Yeah, and so people used to make a day trip out of this and try to cross every bridge exactly once. It's a challenge because if you think about it, if you cross a bridge and then you end up back where you started and there's nowhere bridges leading out of there, then you kind of painted yourself into a corner, right?
00:04:52
Speaker
Yeah. Leonhard Euler decided to look at this problem and analyze it mathematically, and he came up with the first graph theory proof, and it was proven as follows. So Meryl, first, how do we draw this problem as a graph? By now we have this picture that we could think of it as like a map, right? With all these different pieces of land, maybe there's houses on the land, things like that. But how do we make this abstract as a graph? So we can draw every separate piece of land as a vertex, and then we can draw every bridge connecting them as an edge.
00:05:22
Speaker
Yeah, and if you think about this, it doesn't matter really how you dry it at this point anymore. I mean, you can draw a graph at this point as being like little wooden balls connected by string, right?
00:05:36
Speaker
Yeah, something like that. The usual way you see that is on paper with nodes as circles or dots and edges as lines between them. Yeah, exactly. But yeah, so each piece of land that you visit, that's the key thing that Euler noticed, is that if you visit each piece of land, right, it has to have a unique entrance and a unique exit for each time you visit it, right?
00:05:59
Speaker
Right. Because if it didn't, then you'd get stuck there. So this doesn't include the first or the last piece of land, I suppose, but definitely includes the middle pieces of land, right? Right. So at least one piece of land, one vertex, has to have an even number of ridges leading out from it. But the problem is, each one has three.
00:06:18
Speaker
Yeah, and that's something you would have to see on the graph. We might put this on our cover, as part of the cover at least. You could find a diagram of these bridges online, and you'll notice that, yeah, like Meryl said, there's an odd number of edges leading away from each vertex. So that means that the original problem cannot be solved. So there just isn't any way to cross each bridge exactly once? Nope. You gotta cross at least one bridge twice. And yeah, this was back in 1736 when he proved this.
00:06:51
Speaker
All right, now that we got the basic stuff out of the way, let's go through a few different definitions and examples to kind of get familiar with graph theory.
Types of Graphs and Their Applications
00:07:00
Speaker
So Meryl, let's talk about trees.
00:07:02
Speaker
So trees, not like the plant, but called trees because they look like the plant, are a graph where any two nodes are connected by exactly one path. So there's no loops in the graph. And the result of this is that they do end up looking like you have a root node usually and it branches off into leaves that branch off into more leaves.
00:07:22
Speaker
Yeah. And the cool thing about a tree is that you could make any part, any note in the tree, what's called the root of the tree, just by kind of like reconfiguring it. You can imagine this as like, let's say you took a twig on the, on a tree, like that you found in the yard and you put that as, and you planted that in the ground and had everything else soaring above the ground. So you'd have this gigantic bark. So you look very weird, but you could do that with trees and graph theory.
00:07:49
Speaker
We also have weighted graphs and weighted graphs are like a regular graph, right? But each edge is associated with a number. So for instance, some examples of weighted graphs could be, so let's say we have cities as vertices and we have roads that go directly between cities as edges, then the distance of that road could be the weight of the graph. And related tangentially to weighted graphs are directed graphs.
00:08:17
Speaker
And so directed graphs are, instead of two vertices just being connected, we draw an arrow from one vertice to another to show that it's only connected in that one way. And so for a directed graph, we could think, and you probably wouldn't see this in real life, but imagine if two cities had a one-way road between them. So you could go from city A to city B, but for whatever reason, you couldn't go the other way.
00:08:40
Speaker
or the other way might be a longer windy road, right? So the distance in road terms between A and B starting at A and ending at B would be less than starting at B and ending at A, right? Right. And so then we have a directed weighted graph. Yeah. And that's that could be like, you know, the
00:08:57
Speaker
map of the cities, but also with speed limits or distances, assuming that there could be one-way roads. You could also think about all financial transactions, right? You start somewhere, you end somewhere, you have a certain amount, and you can even put a certain time if you want to have another wait on each edge.
00:09:14
Speaker
Yeah, for instance, let's say that people are the vertices in this graph and who owes money to whom represents the directed edges. And so you have an edge from person A to person B if person A owes person B money, and then you could have a weight with that graph that says how much person A owes person B. Yeah. And if y'all owe each other money, I mean, I guess that only happens at the country level and business level, right? People don't tend to owe each other money.
00:09:42
Speaker
Yeah, usually it cancels out. You also have a graph's nodes point at themselves, right? In a directed graph. So that would be like... So let's say you have the graph of people that you're related to within a certain distance. You could be related to yourself there. So that'd be a simple example of that. Another example of that might be that you could travel from City A to City A within City A. Those are kind of trivial examples, but you see the point that we're making.
00:10:11
Speaker
And so this is only the beginning. So we're only really scratching the surface of just how many different types of graphs there are.
Real-World Examples of Labeled Graphs
00:10:18
Speaker
If we went over all of them, this episode would be hours and hours, if not longer.
00:10:24
Speaker
Oh yeah, absolutely. Last couple of properties we're going to talk about in graphs is a little bit more complex, but we're going to talk about the notion of a Hamiltonian path and a Hamiltonian cycle. So what's a Hamiltonian path? So I actually really enjoy this one, because what a Hamiltonian path is, is that it's a path that visits every node of a graph once. Yeah, so it's kind of like the opposite of the bridges of Karinesburg problem, right?
00:10:49
Speaker
Yeah, instead of crossing every bridge once, you're visiting every node once. And so my favorite example of this, actually, because I'm a big fan of chess, is the Knights Tour. The reason this works is imagine that the squares on a chessboard are vertices in a graph, and then any legal knight move between one square and another is an edge.
00:11:10
Speaker
So what we get is a pretty messy looking graph, but what we want to find in it is a way to visit each one of those squares on the chessboard once. And so this is called a Knight's tour, and it's an example of a Hamiltonian path. Yeah, and you can also think of a Hamiltonian path as being a subset of the graph that it's part of, right? A subset that contains every vertex, but not necessarily every edge, and with the condition that each vertex is only mentioned by two edges at the most.
00:11:39
Speaker
And a Hamiltonian cycle is much the same, but not only visits every node, it goes back to where it started. And it exists for every platonic solid. So if you have some D&D dice or some D20 dice that you can part with, and if you want to do a fundamental math experiment, you can find a squiggly path that goes along the edges that kind of traces out the entire die. And there will be no node that isn't visited by a line.
00:12:06
Speaker
This is something you could maybe do at home, but you could look this up also on Google Images or anything like that. So before we talk about the things that can be represented as graphs, we just want to talk about how weighted graphs and directed graphs are types of what are called labeled graphs, right? Which means that either the vertices or the nodes or both can have some kind of data associated with them, whether that be direction or weight or just like an arbitrary color from a set, right?
00:12:35
Speaker
Yeah, so like the nodes in a graph could have different colors associated with them or we could even give them names. Edges can have labels, whether that be again colors, it could also be numbers, like weights and a weighted graph. Yeah, absolutely. So social networks, right, you can have links that mean like is a friend of likes, hates, is a fan of, things like that, right? Yeah. Works for that kind of thing.
00:13:00
Speaker
And another graph data set that I've actually worked with once was there was a list of research papers. They were all published from different departments within a company. And so that was the label of the node. And then the edges of that graph were the co-authors between the different papers. So if they had co-authors, then they were connected.
00:13:20
Speaker
That's pretty fascinating. And yeah, we have also like rivers, sewers, which are weighted graphs. If you weight them by flow, right? Or max flow. Neurons, you can see them as weighted graphs, weighted for how closely they're connected and how strongly they're connected and labeled with the receptor that's used. And you can have the nodes labeled with how much backup neurotransmitters are in there. Orchards in many companies are trees.
00:13:47
Speaker
And for that note on neurons, we actually in the field of machine learning use those kinds of graphs and we call them neural networks. Oh, yeah. And there's a lot of different types and architectures for neural networks. There's long short term memory networks, which have become popular in the last five years. I think they're invented like five years ago, actually.
00:14:05
Speaker
Yeah, so they're used all the time. I mean, they're also used in things like 3D wireframe edges. So that's like when you see a 3D model and it's all lines of software dependencies, right? You want to talk about those?
00:14:18
Speaker
Oh yeah, so let's say that you have software package A and software package B, and so in order to install B on your computer, you need to install A first. So that means you could draw a line from B to A saying that B is dependent on package A. Or you could even recontextualize it, right, as going from A to B, where the arrow means is a prerequisite for.
00:14:40
Speaker
Exactly. Food chains, exchange rates, electronic circuits, blockchain, which is used in cryptocurrencies like Bitcoin. Yeah, all these things can be represented using graphs. Yeah. And you can also draw shapes like polygons, polyhedra as graphs as well.
00:14:59
Speaker
Hey, breaking math fans. First, I want to thank you for listening. I have an important message for everyone. You can start your own podcast right now with Anchor. Anchor lets you create and distribute your own podcast. Just get an idea, record, and upload. It's just that easy. Anyone can do it. I'm on my way to accomplishing my dream, and you can too. Just get on your device's app store and download Anchor. It contains everything you need to make a podcast. With Anchor, you can put your podcast on all the big platforms.
00:15:28
Speaker
Apple Podcast, Spotify, Google Podcast, Amazon, and more. Reach the whole world with Anchor. Best of all, Anchor is free. You have nothing to lose with a free platform. Download the Anchor app or go to anchor.fm to get started.
Euler's Formula: Planar Graphs in Geometry
00:15:47
Speaker
All right, we're gonna dive a little deeper into graphs, and we're gonna start with our friend Euler again. So Euler has this thing called Euler's formula, and we're gonna just state it real quick without explaining it, then explain it. It's V plus F minus E equals two. So what does that mean? Well, we gotta talk about planar graphs, right? Yeah, so a planar graph is a graph that can be drawn on a 2D plane so its edges don't cross each other, so they only intersect at the vertices.
00:16:14
Speaker
Yeah, and so you might think maybe a cube is like this, but if you smush down a cube right on a table, you can do that without the lines crossing, right? It would just look like a square with a smaller square inside of it. Yeah, but that's not going to work for every three-dimensional shape. Yeah, exactly. So like if we have five vertices connected together and we have a complete graph between them, that means a graph where every pair of vertices is connected by at least one edge, that is not a planar graph, right? Because it cannot be drawn on a plane.
00:16:44
Speaker
Yeah, so you can try this if you have a pen and paper. So if you just draw four vertices, try to draw edges between each of them such that they don't intersect. Now try to do that with five, you'll see that you can't. So the reason why is something to do with the Euler characteristic, right? So that is that V plus F minus E thing. So for planar graphs and regular polyhedra, things on a sphere, right, you have V plus F minus E equals two.
00:17:11
Speaker
Yeah. And so I think we also need to talk about what faces are in this case. So we all know if we have a polyhedron, say a cube, a dodecahedron of D12 dice, a dodecahedron, an octahedron, even some star shapes, then we know what a face of that is. It's just one of its sides, right? Yeah. And I guess that would be just a loop that contains no loops within it.
00:17:37
Speaker
Right, and then there's even a way in 2D space to think of what a face is, is that it's a region of the plane that is enclosed by vertices.
00:17:47
Speaker
Yeah, so it'd be like a polygon shape, right? Yeah, so let's say that if you draw just a polygon graph on your piece of paper, then you actually have two faces though. You have the face that is enclosed by that polygon, and then you have the exterior of it as well. That's considered a face. Yeah, so what V plus F minus E is, it's a number of vertices plus a number of faces minus the number of edges, and it's always two for any planar graph. And it was just kind of remarkable, right?
00:18:16
Speaker
Yeah. And if you have like a regular polyhedron, like a platonic solid, then it'll also apply to that. Oh, yeah. And in fact, I'm pretty sure it applies to any 3D model that doesn't have tunnels in it. One thing that becomes clear is that the reason why planar graphs and graphs on a sphere have the same Euler characteristic, right, is because since the exterior is a face, right, then the exterior only exists for a planar graph.
00:18:44
Speaker
If you're doing it on a sphere, the face is really just the rest of it, right?
00:18:50
Speaker
Yeah, so you're kind of thinking of joining the rest of the plane together at infinity, kind of like a Riemann sphere almost. Yeah, and so you can imagine, if you have a plane that is everything, we can take the center of the plane and we can put that on the top of a sphere. And let's imagine that this plane is infinitely stretchy, so you stretch all of it down and tie it at the bottom, kind of like a lollipop, right?
00:19:16
Speaker
Yeah, so the bottom then the south pole of this sphere is infinity. Yeah, meaning all the points infinitely far away from our point at the top other side of the sphere. Yeah. So then you have another region of a sphere that's also enclosed by the edges. And so we have another face.
00:19:34
Speaker
Yeah, and that's why that kind of works that way. But like, yeah, you have this example that we did before the episode started about a Taurus. So if you take a Taurus, let's say you have a glazed donut. Mmm, donuts. And you draw a circle along the top, along the bottom, the inner edge and the outer edge, and then four circles perpendicular to all those. So imagine like where you would grab a donut. Imagine four circles like that.
00:20:02
Speaker
If you put the vertices at the crossings of the lines and the lines themselves between them are the edges, you'll see that there's 16 vertices, 24 edges, and 8 faces, so v plus f minus e equals zero in this case. Yeah, so in this case our torus has an Euler characteristic of zero. Yeah, and there's different Euler characteristics for different types of surfaces, but this would be an entire episode in its own.
Dijkstra's Algorithm for Shortest Paths
00:20:30
Speaker
So now I want to talk about one of my favorite things in graph theory and this is probably a lot of computer scientists favorite thing in graph theory as well is Dijkstra's algorithm named after computer scientist Edsger Dijkstra. What it is is it's an algorithm that finds the shortest path from one vertex of a graph to the other vertices in the graph where we have a weighted graph and we're sort of regarding weights in this case as distances and that's what we mean by the shortest path.
00:21:00
Speaker
Yeah, so we could use this for doing a lot of things. So let's say we have a bunch of computers and a network and we have a certain latency between each computer. So a certain amount of time between when the computer sends a signal and the other computer receives and processes it.
00:21:17
Speaker
So if you want to find the shortest path between one computer and another in this peer-to-peer network, you can use Dijkstra's algorithm for that. And then the shortest path would be the amount of time that it takes a message to go from the first part to the end. You can also probably already see that this could be used really well for finding best routes in map programs. So now I want to actually describe how this algorithm works, and we're going to do so by using cities and roads as an analogy again.
00:21:44
Speaker
So yeah, so we start by defining a city that we want to know the shortest distance between that city and the others, right? Right. So since we're dealing with an algorithm, we have to think about things in terms of lists, and we have to keep track of where the data is, right? Because otherwise it's not very formalized. So let's start with a list of cities to visit. And which cities would we put on this? So we'd put everything but the starting city.
00:22:10
Speaker
Yeah, and a list of visited cities so far, which would be empty. I mean, you could put the city that you're already in, but there's no real reason to do that. Yeah. So what we do is that we also have a list of the distances to every city from our starting city. And we have a list of the last city that we visited to get to each city. In the shortest distance, right? That's right.
00:22:33
Speaker
And so in algorithms, sometimes we kind of start with assumptions and refine them as we go along. So we're going to start by assuming that no city visited each city because we don't have any information on that. So we use a null city or like some kind of fake city, some token like that. And we assume that each city is infinitely far from the starting city, right?
00:22:53
Speaker
Yeah, and then we can also say that the starting city is zero distance from itself if we have that on the table. Yeah, exactly. And so what we do is, so we start obviously at the starting city. What we do is we see all of the cities that have a road directly to another city. And then what we can do is we can, for all of those cities, we can update the distances of all of those adjacent cities to the distances of the roads connecting them.
00:23:20
Speaker
And this is sort of a working city kind of like memory, right? We're kind of like dealing with which city we're working with and we start with the start one, right? Yeah. And then so once we've updated those distances, what we do is we mark our starting city as visited. So we add it to that list of visited cities and then we move on to the closest city. Yeah. And then we do the process again, right?
00:23:44
Speaker
Yeah, so what we do then is that we update all the distances again. And if we find that by some other route, we have a shorter distance than the direct road between cities, then we update the shortest distance between those cities. And then we say that that city that we just visited is the previous city to get to that shortest distance. And we obviously only updated when the distance is less than the one that we already have written down, right?
00:24:12
Speaker
Yeah, otherwise there's no point. Yeah, and that's why we started positive infinity, because which numbers are less than positive infinity? Well, that would be all of them. Yep, all of those cities. And yeah, you just keep doing this over and over again, and eventually you will know the worst case for visiting each node from where you started.
00:24:30
Speaker
Yeah. And so what you know actually is the shortest distance to that city and the last city visited to get to that city. So using that, you can draw a path from one city to another and get the shortest possible path. And doing this, we actually, if you take into account every city, then you get a tree out of our graph. And what it does is that that tree gives us all of the shortest paths in this graph.
00:24:57
Speaker
Yeah, meaning if you go along each road that's in the tree, at no point will you have taken any more than the minimum amount of time to get to each place. Exactly. And it has time complexity of O of V squared, meaning that if you, for example, double the amount of vertices, it'll take about four times as long to run. If you triple, then it'll be about nine times as long to run. You basically square the number of vertices.
00:25:20
Speaker
A way to think of this is that so you visit every city once and from every city that you visit, you look at, in the worst case, every other city once. So what is the diameter of a graph then?
00:25:32
Speaker
So it's the longest shortest path in a graph. Yeah, so we can do this like model the social distance between acquaintances between people and surprisingly small. There's a study where they took 240 million people on Microsoft and 30 billion other conversations. It turned out that starting at one person, there are only six links between any two other people.
00:25:53
Speaker
You could also see this kind of stuff in Wikipedia, right? I challenge you to start at the Wikipedia article for Peanuts and make it to the Wikipedia articles for Rosa Parks, Chess, Beer, and Prog. It's easier than you might think.
00:26:11
Speaker
Just a fun little tidbit because I remember this, if you click the first non-italicized, non-parenthesized link in every Wikipedia article, eventually it will lead back to the Wikipedia article for philosophy. Yeah, and it's something like 90% of articles, but still, it's way, way a ton of them. The articles that don't do that pretty much are stubs. And it wasn't planned that way either, it just happened.
The Four-Color Theorem and Computer-Aided Proofs
00:26:36
Speaker
So our last section is on map coloring theorems. So to set the stage, imagine you have a map, right, of let's say states in Mexico. So each state borders a certain number of other states, right? Right. So let's draw each state as a node and each border as an edge. So for example, Sonora borders Chihuahua, right? So it would have an edge between those two. So it won't look exactly like the original map like at all, but it'll represent each piece of information.
00:27:03
Speaker
So map coloring would be, let's say you color Baja California blue and you do Sonora like green and so on. You might wonder how many colors you need to color a certain map. And intuition might tell you that for more complex maps, you need more colors. And for less complex maps, you need fewer colors. And while this is generally true, it turns out that for any planar map that could be represented using a planar graph, you'll only need four colors to color it in, which is kind of surprising, right?
00:27:31
Speaker
Yeah, and would you like to elaborate some then on the proof for this theorem? Yes, absolutely. So there was some proof that people tried to do, right? So Alfred Kempe in 1879 did a certain proof that basically said that like if you have a node that's connected to more than four nodes, then you can just cycle the colors around the node, right?
00:27:51
Speaker
His proof was stood for 11 years until it was shown to be erroneous. Peter Guthrie Tate did the same thing in 1880 and his was shown to be erroneous in 1891. So then another proof wouldn't be a claim for more than a hundred years where Kenneth Apple and Wolfgang Hocken at the University of Illinois announced a proof on June 21st of 1976. And do you know anything about this proof, Meryl? Um, not particularly. You go ahead.
00:28:14
Speaker
Yeah, it was very controversial because it used a computer to prove something and it generated 400 pages that needed to be verified by hand. Basically, it used a mathematical technique called discharging, which is where you have a bunch of graphs that satisfy certain properties that altogether prove something about a whole group of graphs, right?
00:28:34
Speaker
He was able to generate 1,834 graphs that certain properties had to be associated with if the graph, if planar graphs needed more than four colors to be colored. Later he reduced that to only 1,482 different solutions. And it was also controversial because mistakes were found, but then they were fixed. And that's a weird thing about really long math proofs is that there often be a mistake that somehow is a-patched. It's kind of weird, right? Yeah, and this proof sounds awfully exhaustive.
00:29:00
Speaker
Oh yeah, absolutely. It's also not very satisfying. I mean, it's cool to know, definitely, but it doesn't have very much oomph. The longer the proof, the less oomph.
Conclusion: The Impact of Graph Theory
00:29:15
Speaker
Graphs are used to describe networks of all kinds, and applications of their properties have been used extensively in the last century or so, used by mathematicians, programmers, and engineers alike, perhaps testament to the universality and even ephemeral nature of graph theory.
00:29:29
Speaker
I'm Sophia. And I'm Meryl. And you've been listening to Breaking Math. Quick plug, go to Facebook.com slash Breaking Math podcast, click on store and see if you want our poster. It's cool. What I learned from this episode is that true graphs were the friends we made along the way.