1. Podcasts
  2. The Joy of Why
  3. How Does Graph Theory Shape Our World?
The Joy of Why

26 Jun 2025 · 34m · 15 chapters

Episode artwork

How Does Graph Theory Shape Our World?

In short

Graph theory’s origins (Euler’s Königsberg bridge problem) and how it leads to coloring problems and the Strong Perfect Graph Theorem about “perfect graphs” (chromatic number equals the largest clique size). The episode also contrasts discrete vs continuous thinking and discusses how abstract math can still model real situations like seating arrangements and map-coloring.

Guests

Maria Chudnovsky, a graph theorist at Princeton University. Background: born in Russia, moved to Israel as a teenager; works on graph theory and helped solve a decades-old problem related to Claude Berge’s strong perfect graph conjecture. She’s known for a proof published after collaborating with others including Al Seymour.

Key claims

Euler proved the bridge-walk is impossible by parity (odd-degree vertices). Perfect graphs match clique size to chromatic number. Chudnovsky and collaborators proved the strong perfect graph theorem; the proof uses decompositions into cases/“pieces.”

Notable examples

Königsberg (Kaliningrad) bridges; wedding seating as graph coloring; four-color theorem on maps; “high-genus” (donut/pretzel) maps where four-color reasoning fails.

Written by AI. May contain mistakes.

Chapters

0:35

The Bridges of Königsberg Problem

Discussion on Euler's approach to the Königsberg bridge problem.

“And this is The Joy of Why, a podcast from Quantum Magazine, exploring some of the biggest unanswered questions in math and science today.”
1:24

Mathematics as Reasoning

Exploration of how Euler viewed the problem and its implications.

“Sometime in the 1700s, Leonard Euler was asked this question.”
2:06

Introduction to Graph Theory

How Euler's work led to the development of graph theory.

“Now, Konigsberg is now the Russian city of Kaliningrad, if I've got that right.”
4:00

Changing Perspectives on Mathematics

Discussion on the evolving perception of mathematicians in society.

“We realize we're only a few blocks apart.”
5:32

Mathematics as a Universal Language

Exploring the idea of mathematics as a universal language.

“There's also an old idea that mathematics is a language of the universe, which might actually be attributed to Galileo.”
6:31

Personal Experiences with Language and Math

Maria's background and how it shaped her view on math and language.

“Another thing math brings to the table is clear thinking.”
7:42

Defining Graph Theory

Maria provides an explanation of graph theory and its applications.

“I'm sure the fact that of all the subjects I could study, the one that required the least command of a language was math, had a lot to do with my choice of field of study.”
9:35

Exploring Types of Mathematics

Discussion on the differences between discrete and continuous mathematics.

“What drew you to this particular topic of graph theory?”
12:04

Practical Applications of Graph Theory

Maria shares a personal story of using graph theory for her wedding seating chart.

“continuum between two integers is you can remove an infinite number of rationals and still have an infinite set left over.”
14:00

Graph Theory and Wedding Seating

Explore how graph theory applies to real-life scenarios like wedding seating arrangements.

“were people I didn't really know from my husband's side.”
Show all 15 chapters
24:25

The Strong Perfect Graph Theorem

Learn about the strong perfect graph theorem and its implications in mathematics.

“You know, you never know until you know.”
28:01

The Nature of Problem Solving

Explore how mathematicians choose problems based on personal interest rather than difficulty.

“You have some huge overwhelming thing, but you're simplified it into a scenario where it's always like this and a scenario where it's always like this and scenarios, it's always like that.”
30:08

Personal Insights into Mathematical Joy

Discuss the personal joy found in research and connections to past experiences.

“Maria, thank you so much for joining us.”
31:18

Diverse Motivations in Mathematics

Reflect on how different personalities influence the approach to mathematics.

“And as Maria says, it's an aesthetic choice for her.”
32:05

Creative Processes in Mathematical Thought

Delve into the analogy between mathematical reasoning and artistic creativity.

“I mean, actually, what personally drives me has always been paradox.”
A man walking through an airport, asking his phone a question

Ask about this episode

Get the gist, explore an idea or ask about something said.

Claude

On The Joy of Why, what are the key points of this episode?

Searching your listening

Transcript

Automatic transcript. May contain errors.

0:01Take your curiosity with you on KUOW's new podcast, Pocket Science. In each episode, we catch up with local scientists in the lab and in the field to find out how they're pushing the boundaries of what we know. From the surface of an icy moon of Saturn to the inside of a human brain on psychedelic drugs. The answers might surprise you. Listen to Pocket Science on the KUOW app or wherever you get podcasts.

0:34I'm Jana Levin. And I'm Steve Strogatz. And this is The Joy of Why, a podcast from Quantum Magazine, exploring some of the biggest unanswered questions in math and science today.

0:50Steve, hi. Hi there. How are you doing, Jana? Good. It's good to see you again. Yeah, great to see you. I have a math problem for you. Oh, love it. So imagine you're visiting a city and it has a river, maybe, let's say, maybe it's an island like Manhattan. And there's little islands like Randall's Island or Roosevelt Island, and they're connected by bridges. Uh-huh. And you're a tourist. You want to cross every bridge, but you don't want to overexert yourself, so you're going to try to cross each bridge once. Mm. Have you heard of this before as a mathematical problem? You know I have. Yeah. Seed planted.

1:23Yeah, yeah. No, it's a classic problem. Sometime in the 1700s, Leonard Euler was asked this question. You know, a funny thing about it that I only recently learned is that when the mayor of that town, Königsberg, asked him to think about this question, Euler complained, what are you asking me for? This is not a math problem. Right. Isn't that interesting to him? Yeah. This was not math. That's really interesting. At the time. He founded a new branch of math in thinking about it, but he didn't see it as math at the time. So how did he get interested enough to mathematize the problem, which is really what we're doing a lot of the times?

1:57I think it's just that Euler felt that it was a curious question worth thinking about just because it involved, as he put it, reasoning. A puzzle. It was a puzzle, yeah. Now, Konigsberg is now the Russian city of Kaliningrad, if I've got that right. So can a visitor there figure out how to go across? There's a river, there's a mainland, there's two islands and seven bridges. Yeah, that's right. And in that old problem, the townspeople used to go out on Sundays and take strolls, and it was an amusement to see if they could walk across each bridge exactly once. And no one could ever do it, but nobody could prove it was impossible, until Euler, who did prove it was impossible.

2:36And so how does he turn this into a math problem? Well, if you look at his original paper, what he does is use letters, capital letters for the land masses and lowercase letters for the bridges. And then he plays around with the combinations of these uppercase and lowercase letters that would correspond to admissible walks. Oh, how interesting. Nowadays, we would use dots and lines. So, of course, he found that he couldn't do it because some of the landmasses had an odd number of bridges touching them. So once he solves that problem, he realizes, oh, immediately he can say, if this problem crops up again, you need an even number of bridges.

3:10So he's already making headway towards generalizing. And so you said it invented a whole new branch of mathematics. And what's that branch? Well, we call it graph theory. Or if we're in England, we would say graph theory. Well, here we were talking to Maria Chudnovsky, who's a really interesting mathematician at Princeton. She works primarily on graph theory and managed to solve a very interesting, outstanding problem that was nearly 50 years old about perfect graphs. That's a term I haven't heard before. I'll let her sort of tell the story, but it's really about color coding and visualizing and nodes and dots and connectors.

3:49So let's hear from Maria. You want to eavesdrop a little bit? I'm all ears. Great. Here's Maria Chabnovsky from Princeton talking about graph theory.

4:00Maria, welcome to the show. It's so nice to have you on. Thank you. I wish we could be in the same studio. We realize we're only a few blocks apart. Maybe next time. Maybe next time. I actually was amused to discover that you had been in a TurboTax commercial. That's right. That's my claim to fame. I also did a mattress commercial. Did you know that? Yes, I saw you sleeping in a mattress commercial. Exactly. Smart begins with better sleep. There's no statement I believe anymore. They're getting free advertisement with us here. I was amused to see that they listed you underneath your name in these commercials as a superstar mathematician.

4:37And I wonder if you think the culture is changing and our attitude towards mathematicians. I think there's a lot more understanding now of how important math is. I used to tell people, I'm a mathematician, they would say, oh yeah, terrible in math, math is really boring. And now they say, oh wow, that's really interesting. What do you do? I think, you know, with the advance of technology and the internet and, you know, obviously our life has changed a lot over the last 30 years or 100 years, depends how you want to think about it. And I really think math is kind of gaining popularity and gaining traction.

5:12It really is interesting that mathematical literacy or scientific literacy is considered important, more than it used to be, at least. I'm so happy about that because, you know, it really seemed to be an educated person. You need to read books. You need to know something about art. And I would never say that's not important. But now it seems that there's another component to it. And, you know, given that that's a huge part of my life, I'm very, very happy about that. There's also an old idea that mathematics is a language of the universe, which might actually be attributed to Galileo. What do you make of this quote?

5:46I mean, do you see it as a universal language of sorts? I certainly do in many ways. Like, you don't need to speak any particular language very well in order to be able to effectively communicate mathematics. If you have something interesting and important to say in math, you need to have some basic common language as the person you're speaking with. But you don't need to be eloquent. You don't need to be a great speaker. You can just write down what you have to say and say what you have to say, and it's been communicated. There's no kind of added layer of, I need to say it in such a way that it convinces them.

6:23If you have a proof, it convinces them. It doesn't matter how you say it. And it's the same around the world. And it's the same around the world. Yeah, there's really no differences. Another thing math brings to the table is clear thinking. That's maybe a little less of a language thing, but the way you understand things, the way you think about things, you try to break it into pieces and see what's important, what matters, what was incidental and coincidental and not important. If you're used to thinking in a mathematical way, that really puts you at an advantage. It's like a meta-language, like a way of understanding the world that transcends the grammatical structure.

7:01Right. There are all these studies that depending on what language you think it, you perceive the world a little differently, which I'm incredibly fond of. That's amazing. I was actually going to ask you about that hypothesis in linguistics, that language structures your thoughts. So I'm fluent in two languages and I understand three languages. And I know this about myself. Things change a little bit in the way I think when I'm dealing with a different language. Fascinating. I understand that you did have a personal experience with languages, with countries, with moving. You were born in Russia and moved to Israel as a teenager.

7:34So this played a personal role for you, this issue of language, transcending language and using math as a medium to express yourself. Absolutely. I'm sure the fact that of all the subjects I could study, the one that required the least command of a language was math, had a lot to do with my choice of field of study. As a mathematician and a scientist, if you're used to thinking mathematically, then you perceive the world in a certain way, which is a little bit like if you're used to thinking in a certain human language, then you perceive the world in a certain way. I don't want to completely leave this idea too quickly.

8:07I wonder how math can structure your thoughts. The particular field that you choose can structure your thoughts. You're in a branch of math known as graph theory. Can you give us just a quick explainer of graph theory to anchor us in your subject? Sure. Graph theory is a branch of math that studies pairwise relations. Let's start with something in the world. Suppose you have a system that consists of objects, and some pairs of objects are in a relation and some are not. Like you can have a bunch of people, and some pairs of people are friends, and some pairs of people are not friends. or you can start with buildings and roads between them.

8:41Or you can have a bunch of cities, and some pairs of cities have direct flights, and some pairs of cities don't have direct flights between them. So all these things are examples of graphs where you can take objects and then say, this pair is in relation, it goes together, this pair doesn't go together. So now forget all these examples and just stay with the abstraction where you put a dot on your piece of paper for every object, and now you put a line between two dots. We call it an edge if these two objects were in relation. So now you have an abstract mathematical object called graph. Apparently, Euler came up with this idea in 17-something.

9:21And now instead of studying a system of people's friendships or a system of flights or a system of roads, you can just study this abstraction of a graph. You're no longer a social scientist or a transportation expert. Now suddenly you're a graph theorist. Right, you're a mathematician. What drew you to this particular topic of graph theory? And also, do you really think you think more visually and differently because you're so embedded in graph theory? Or you think it was the other way around? You were inclined to visual thinking and that drew you to graph theory. I think the answer is we'll never know.

9:51When I was applying for grad school, I knew I wanted to do discrete math because when I was in college, these were the courses that somehow were easiest to me. I felt that I understood them the best. Like when you take a class, some classes you study, you prepare for the test, you get your grade, and you're grateful it's done. Some classes really stay with you and you keep thinking about it. It's kind of just the tip of the iceberg, and then you keep going deeper and deeper in your mind. And then when you show up for the test, you didn't even need to study because you understood it so much better than what they tried to teach you.

10:23And so classes in discrete math were like that for me. I personally love discrete math. I once had a friend who said, there are different kinds of math. Like, this is a surprise to people who don't live in this world, that there are different kinds of math. Can you help our audience with the difference between sort of continuous and discrete? Sure, right. Roughly, you can partition all of mathematics into two parts. One part is things where you can say, this one is the next one after that one. And then things where you can't say that because between every two things, there's another one. So I'll give you an example though, because of course, if you didn't know what I meant before, you don't understand now either.

11:06Let's say I'm thinking about counting numbers, natural numbers. So immediately after one comes two, immediately after two comes three. And that's discrete. There's no counting number between seven and eight. Now let's think about fractions. Between one and two, there's one and a half. Between one and one and a half, there's one and a quarter. Between one and one quarter, there's one and eight. I'm not going to continue, but I think we get the gist. The first example was a discrete example. The second example is a continuous example. Courses in discrete math were somehow better for me. I always enjoyed them better.

11:39I understood them better. And so when I was applying to grad school, it was clear to me that I was going to do some kind of discrete math. Then I got into Princeton, where the kind of discrete math they were doing was graph theory, and I became a graph theorist. Had I gone to a different university, I would have probably done something else. And maybe I would have been good at that, or maybe I would have had a different career. You might not have made it into a mattress commercial. Exactly. One of the aspects you mentioned, just as an aside, I think is so fascinating about the continuum between two integers is you can remove an infinite number of rationals and still have an infinite set left over.

12:17I mean, the beauty of discrete math is really mind-blowing. On another note, I think it's interesting for people that a graph here is a very visual subject. I often see that you're drawing pictures on the board and making connections. You're doing them very fast because you're so used to it. But how strong is the visual aspect for you in your actual work? How much are you actually using a kind of visual mapping, do you think? all the time. I only think in pictures. Eventually, I have to sit down and write it because otherwise you miss things and you make mistakes. But all the development of ideas is visual.

12:56And it's quite beautiful to watch. Now, a lot of people also wonder what mathematicians are doing all the time. Doodling. What's at stake for the mathematician? Why are these problems important? There's this sort of tension between the very abstract mathematics, which I believe you very much love and real-world application, but what is that balance like for you? What's really at stake for you as a mathematician? I mean, I do abstract math. I'll be very happy if somebody someday finds applications for what I do. You know, sometimes if people come to me and they have a question I can help them with, and it has something to do with the real world, that's exciting, that's fun, I like it, but my world is completely abstract.

13:39Do you ever have to use graph theory to solve your own real-world problems? So when I was getting married to my husband, we had to design a seating chart and we were nervous about it. And I said to him, let me try to do it. You can't be too picky about it. But I took our list of guests, which by the way, the vast majority of guests at our wedding were people I didn't really know from my husband's side. I only knew kind of some stories about them. But it's a graph theory problem. What you do is you make a graph where the vertices, the dots, are the people. And now you put an edge between two vertices.

14:19If these two people are such enemies that you can't put them at the same table. And now what you need to do is take your graph and partition its vertices into subsets so that in each subset, you don't have two people assigned to the same table that can't sit together. You don't have two vertices joined by an edge. And if there are a lot of edges in your graph, that's a hard problem. But if there are a few edges in your graph, namely most of your friends and family get along, then it's actually easy. You can use something called the greedy algorithm and it just works. You know, our friends and family are reasonable people.

14:55There are not so many edges in this graph. So I took this list and a few minutes later I had, it's called the coloring of the graph, the sitting arrangement, tables of 10 to 12. And it was basically completely acceptable. My husband was very surprised by that. Your wedding went without incident. No, no, no incident. Now, you've just been describing graph coloring, right? You're color coding. This is the group, and here's a different group. As soon as you get to a point where, oh, this person can't sit next to this person, you need to assign a new color. Now, this graph coloring, is this a very old human problem?

15:31It absolutely is. There's probably the most famous problem in graph theory, the four-color theorem, which was actually posed by a cartographer 200 years ago. And what he posed is that for any map on Earth, you can color in such a way that two countries that share a border get different colors. So you can do that by using at most four colors. No matter how the world is partitioned into countries, you can color it with four colors in such a way that countries that share borders get different colors. It's not obvious. It is very, very far from obvious. It inspired a lot of mathematical research for dozens of years.

16:08It's very far from being trivial. But let me just say a few things. One is when you say two countries share a border, they really need to share a little interval of a border. Sharing just one point doesn't count. Thing two, this is only true if the countries are connected. If you have a country with islands, that's false. And the third thing is, you know, I said every map on Earth. I amuse myself with that. That's not just an expression. If your map is not on Earth, if your map is on a planet that has high genus, like a donut or a pretzel, then it's not true. So if it's multiply connected in some way.

16:41Right. Not simply connected. So how fascinating. There is right there a real world application, which is trying to understand maps and borders. Maps in the 19th century were very important in terms of beginning to understand and think spatially. You've had a very big impact in an area that describes perfect graphs. Can you explain to me what makes a graph perfect in terms of coloring? I'm so glad we started this by talking about graph coloring, because this sets the stage perfectly for talking about perfect graphs. So you have a graph, it has vertices and edges, and now you would like to color it.

17:20So you want to partition the vertices into sets so that there's no edge inside a set. Another way to say it is you color the vertices with different colors, and the rule is vertices of the same color are not joined by an edge. If two vertices are joined by an edge, they get different colors. Okay, so far so good, but here is a coloring. Color every vertex with a different color. That is not a very interesting concept. To make it a little less abstract, imagine you have to pay per color, and you don't want to buy more paints than you need. Okay, so now the question becomes, if I give you a graph, how many colors?

17:56do you need in order to be able to color it? That's called the chromatic number of a graph. First of all, algorithmically, it's very hard. If I give you a graph and ask you, how many colors do you need? What's the smallest number of colors with which you can color this graph? You, in general, can't give an answer in a reasonable amount of time. Okay, but another thing is maybe I can look at a graph and start connecting how many colors I need to other properties of this graph. Maybe I still won't be able to give you an answer, but here's an obvious lower bound on the number of colors you need. If I have a graph and in it there is 100 vertices all pairwise adjacent, I need at least 100 colors in order to color this graph.

18:33Now there are graphs with no three pairwise adjacent vertices that need a thousand colors and there are graphs with no three pairwise adjacent vertices that need a million colors. Now on the other hand there are graphs where that doesn't happen. There are graphs where this obvious lower bound of how many pairwise adjacent vertices you have is actually the right answer. And these are called perfect graphs. I get the gist of it. And let me just try to help for our audience to bridge a little gap. It's my understanding that when you have these, you're calling them pairwise adjacent vertices, we could call those a click.

19:07Yes. Click is the right word for it. I'm just imagining that socially people understand when you're trying to do a wedding graph or a dinner party graph that there's a little click. And in that click, if that number of vertices equals the number of colors you need to use through a chromatic number, then you're on your way to a perfect graph. So a graph is perfect if its chromatic number equals to the largest size of a click in it. Oh, excellent. Exactly. So the largest click, yes. Now, in the 1960s, a French mathematician, Claude Berge, began to think more about coloring and perfect graphs. He formulated this conjecture known as a strong perfect graph conjecture.

19:45Now, this has loomed large in your work. How does your work tie in with this famous conjecture, long-lasting conjecture over 50 years? So when I came to Princeton as a graduate student, I came to the office of Al Seymour, and he was working on the strong perfigráfic conjecture at the time. And I knocked on his door and I said, can I work on this with you? And I think he was a little surprised. It's not a question people often ask, but he didn't know what to say. So he said yes. And then a couple years later, four of us solved this problem. It wasn't my first theorem, but it was the first theorem I proved as a PhD student, and it was a good way to start a career.

20:22That must have had an enormous impact, a half-century-old conjecture, many people working on this important problem. How did you approach this, you and your collaborators, so that you were able to make progress where others were stymied? That problem was open for 40 years at the time, and people worked on it, Berger's conjecture was every graph with this and that structural property is perfect. And it was clear that if and only if a graph is perfect, then it must have those structural properties. You know, when you just say a sentence like that, you have no idea where to separate. How would you prove that everything with those three properties have that fourth property?

21:04But what you could try to do is try and understand what all graphs with these first three properties look like, and then take that and deduce from that the forced property you're actually interested in. Because people have been thinking about this problem for 40 years, there were a lot of ideas of how this gap may be breached. None of them were exactly correct. In the end, we had to come up with our own correct intermediate statement. But there was enough thoughts in the world that at least we knew in which direction we should start going. And then, you know, we worked really hard. We got lucky.

21:47We are smart. All kinds of things. So I love how that refers to a larger global collaboration, which I think relates to something we were talking about in the beginning, about the transcendence of mathematical language, that this is an international collaboration, even if not in an individual paper, in the larger scheme of things. Very much so. I mean, I work with people from all over the world. I travel a lot. And because math is math and truth is truth, you can disagree on everything, but you will agree that the proof is correct or you will agree that the proof is not correct and your other opinions don't play into it at all.

22:27I love how she says it. Math is math and truth is truth. But it makes me wonder if this kind of training that we get tears us ill for the real world. Maybe you could say the real world is overrated. You know, that's what some of us think in math. Because how many other places can you say something like that? Math is math and truth is truth. I mean, this is an oasis. It's such a pretty place to live. It's such a pretty place to live. And we talk about this a lot on the show, just how transcendent the ideas are. They're true for all of us. And that's really special and really unusual. It's also a gift that we get to talk to each other across the centuries.

23:06You know, like we mentioned Leonard Euler. And you can have in your mind at least a conversation with someone from hundreds of years ago. There are some differences, but there's a lot that we have in common. Absolutely. I love that idea that we're having a dialogue across time. I mean, not only across cultures. Right. Right. Not only across the globe, but we can actually go across time. I mean, this is when we talk about sending messages out into the universe, the most reasonable messages to send are ones that have to do with math. Let's go back to our guests. Let's hear more from Maria right after this break.

23:57Welcome back to The Joy of Why. We've been speaking with graph theorist Maria Chudnovsky on how she proved the strong, perfect graph theorem, something that was proposed by Claude Berge back in the 1960s. Math can be very frustrating, and it can take a very long time. You have this enormous breakthrough, but it's not a single moment. For you, how does this unfold and come clear to you that you were really on to something? You know, you never know until you know. You really think you're making progress. You set your next goal and you proved it. And now you think, okay, well, great, this was a big hurdle.

24:36Now it's a straight line from here. Then suddenly it's not a straight line. It's a nerve-wracking process. But on the plus side, there are a lot of little celebrations. Just because it's not the last hurdle doesn't mean it wasn't an important one. Every step is a eureka moment. I think now every proof is very complex. There's not one eureka moment. But there are a lot of victories, a lot of celebrations. Ingrid Dobyshek, in some interview, once said, the reason we do math is because we're addicted to the high. And it's completely true. That's a t-shirt. I don't know if the story is true or if it's apocryphal, but I heard that Berge was read the news of the impending proof while he was in the hospital.

25:12Is that a true story? You know, he was in the hospital. That's true. He was told the news in his last days when we found the proof. He was told about the proof. It's a nice dimension. And of course, mathematics is ultimately a human pursuit. I wanted to ask a little bit about applications that have branched off of this discovery. Are there, to your knowledge, examples in which people are using this in other fields? Right. So the answer is, I don't know. There is a paper about profit graphs and coverage collection in Brooklyn. How grateful I shall be to you if that problem is solved. There we go.

25:49Exactly. But it's not me. It's before my time. I definitely do not need for there to be a practical application to value mathematics. And I love that we're asking people to appreciate that the stakes are high, even for very abstract mathematics. I know that we have sirens in the back, so there's probably some graph theory problem for solving the route that an ambulance or cop car has to take through Manhattan. You know, designing optimal routes is definitely a graph theory problem, right? You have junctions and roads between them, and that's a graph. And now you're trying to find the best way to navigate that graph.

26:25So let's take this back to the way you approached your solution. The problem that you approached, how long, for instance, is the paper that you wrote? About 150 pages long. Okay, so this is very long. This is very long. This is hard. This has nothing to do with complexity hierarchy. This is just hard. This is just colloquially hard. How did you simplify the problem? There seemed to have been a strategy where you broke the graphs into pieces in a systematic way to allow you access to this proof. All right. So there's a lot of breakage going on. So the goal was to prove if you have two properties, then you're perfect.

27:06So what we did was we showed that if you have these two properties, then either you have some graph we can describe or what's called an explicit construction. or you can break your graph apart in such a way that showing that this half is perfect and showing that this half is perfect is enough. So that was the theorem we proved. This is the theorem with a lot of outcomes. We have five explicit constructions, three kinds of decompositions, three kinds of ways to break a graph. So what you're proving is if properties 1 and 2 hold, then one of those eight things happen. Now, in general, that's a theorem that's very hard to prove because you don't know which way to push.

27:46Are you trying to prove that the graph behaves like this or are you trying to prove that it behaves like that? So what's helpful is to break the world into pieces where in this part of the world, it's always like this. In this part of the world, it's always like that. And in a way, that's the key to almost every mathematical proof. You have some huge overwhelming thing, but you're simplified it into a scenario where it's always like this and a scenario where it's always like this and scenarios, it's always like that. And if you can distinguish between your scenarios, then usually that leads you to a proof.

28:19And so that was kind of a very important insight, a very important thing to do in this proof to understand how to approach the world in this stratified way. It's a strategy. Right, right. So it's fascinating. Maria, I wonder, how do you know when you're approaching a problem, How hard it is. Is the next problem you brave going to be a necessarily even harder one? Or are the challenges unpredictable? I don't think problems are linearly ordered by difficulty. I think every problem is hard until you solve it and then you have a solution. The reason to choose a problem is not because it's harder than the previous problem you solved.

28:57The reason to choose a problem is because there's a phenomenon you want to understand. And in order to understand it, you need to answer this question. If the question is appealing to me, it's an aesthetical choice. You know, it's a little bit of a practical choice if I think I have a chance of contributing. But it's also like, does this question interest me? And so what is that intuition? What drives your choices in big problems? I think, and this is speculation, questions that interest us are related to questions we already thought about. It's very rare that somebody, you know, comes into the room and says, here is a question you must be really interested in.

29:36And if I've never thought about it, what does it have to do with me? So I think there's like some kind of world you're building throughout your lifetime. And every next question interests you because it relates to the world you've built so far. But I think it's probably only clear to you from the outside. I think it's a little less obvious. I wanted to ask you one last question, and that is, what brings you joy in your research? Seeing order in a new place, understanding that something is actually built in a way I can describe, even though until recently it was just a mess, I guess, bringing order to the mess.

30:23Beautiful. Maria, thank you so much for joining us. So there's such a depth here. I could talk to you for hours. Thank you very much for having me. I really enjoyed this. I'm struck by how personal the experience of being a mathematician is, because when she says that what interests her is not necessarily how difficult the problem is, but whether it connects to things that she's thought about before, I feel like that's not a universal phenomenon. on. That's something that some of us would use. But I'm thinking, let's say, of John Nash, the great mathematician profiled in Beautiful Mind, who would change fields just looking for the hardest unsolved problem.

31:09It was a macho thing for him. I think he was interested in everything as long as it was hard. I mean, isn't that also the testament that it takes all kinds of personalities and ways of thinking to make an entire discipline, right? A healthy discipline. Exactly. And as Maria says, it's an aesthetic choice for her. Some people are driven by aesthetics, but I think some are driven by, I want to use my craft. I have this powerful technique and I'm just looking for something I can use it on. Yeah. Do you feel that challenge and difficulty intrigues you when trying to solve something? No. No. Interesting.

31:44No. I really resonated with what she said about phenomena. It really hit me that she uses the word that a scientist would use, not a mathematician, that she sees phenomena and it's phenomena that appeal to her and she wants to think about things that seem curious and baffling, but that are close enough that she thinks she could contribute. So I love that view of it. That's much closer to my own. I mean, actually, what personally drives me has always been paradox. Oh, intriguing. I really like it when something seems wrong, when something is off. That shouldn't be the way this works? That's the kind of question I always like.

32:22Right. And then you can't not follow it. Yeah. You know, I think sometimes I like these kind of big visual problems with a lot of math, right? A lot of geometry, a lot of big spatial moves, big brush strokes that move things around. I'm taken with your analogy to painting. Do you actually paint? Oh, gosh. I mean, a long time ago, but I don't advertise myself as a painter, but it's true. There's a method, right? You go up and you do big brush strokes. And then you do, you get ever finer. Eventually, you're on your two-hair brush. Well, it's really great talking to you about all this, Hannah. Yeah, great talking to you, Steve.

32:56Till next time. Okay, bye-bye.

33:02If you're enjoying The Joy of Why and you're not already subscribed, hit the subscribe or follow button where you're listening. You can also leave a review for the show. It helps people find this podcast. Find articles, newsletters, videos, and more at quantamagazine.org. The Joy of Why is a podcast from Quanta Magazine, an editorially independent publication supported by the Simons Foundation. Funding decisions by the Simons Foundation have no influence on the selection of topics, guests, or other editorial decisions in this podcast or in Quanta Magazine. The Joy of Why is produced by PRX Productions.

33:40The production team is Caitlin Foulds, Livia Brock, Genevieve Sponsler, and Merit Jacob. The executive producer of PRX Productions is Jocelyn Gonzalez. Edwin Ochoa is our project manager. From Quanta Magazine, Simon France and Samir Patel provide editorial guidance with support from Matt Karlstrom, Samuel Velasco, Simone Barr, and Michael Cagnugolo. Samir Patel is Quanta's editor-in-chief. Our theme music is from APM Music. The episode art is by Peter Greenwood, and our logo is by Jackie King and Christina Armitage. Special thanks to the Columbia Journalism School and the Cornell Broadcast Studios.

34:23I'm your host, Jana Levin. If you have any questions or comments for us, please email us at quanta at simonsfoundation.org. Thanks for listening.

34:44From PRX.

From the publisher

Born in the 18th century when Leonhard Euler solved the puzzle of the seven bridges of Königsberg, graph theory has become a foundational tool in mathematics. It studies relationships through nodes (vertices) and the links (edges) that connect them, transforming the complexity of systems — from friendship networks to airline routes — into elegant abstractions that reveal underlying structure and interaction.

Maria Chudnovsky from Princeton University is a leading mathematician in the field. In this episode of The Joy of Why, Chudnovsky talks with co-host Janna Levin about how she got into graph theory, solved the decades-old perfect graph problem, and used it to plan her wedding seating chart. Chudnovsky also reflects on her appearance in commercials as a “superstar mathematician,” and how her background primed her for a discipline that transcends language, culture and time.

More from The Joy of Why

All episodes