Graph theory

Key people

• Leonhard EulerSwiss mathematician, physicist, and engineer (1707–1783)
• Paul ErdősHungarian mathematician (1913–1996)
• Arthur CayleyEnglish mathematician (1821-1895)
• Kazimierz KuratowskiPolish mathematician (1896–1980)

Timeline

• 1860The autonomous development of topology from 1860 to 1930 fertilized graph theory back through the works of Camille Jordan, Kazimierz Kuratowski, and Hassler Whitney.
• 1935Enumerative graph theory then arose from the results of Cayley and the fundamental results published by Pólya between 1935 and 1937.

Read

• Introduction to graph theoryRobin J. Wilson · 1972Book
• Graph theory and its applicationsJonathan L. Gross · 1999Book
• Graph theoryFrank Harary · 1969Book
• GraphentheorieReinhard Diestel · 1997Book

Watch

• Introduction to Graph Theory: A Computer Science PerspectiveReducibleVideo
• Graph Theory | Overview & Basic Terminology Of Graph Theory | Discrete Mathematics By GP SirDr.Gajendra PurohitVideo
• MA25C14|MA3354|DM|Graph Theory Introduction in Tamil|Graph Theory Basic DefinitionsMathematics KalaVideo

Listen

• Deep Questions with Cal NewportCal NewportPodcast
• Collège de France - SélectionCollège de FrancePodcast
• Practical AIDaniel Whitenack and Chris BensonPodcast
• a16z crypto showa16z crypto, Robert Hackett, Sonal ChokshiPodcast

Voices to follow

• Lalit Kishore Vyas@lalit_k_vyas · XMachine Learning Researcher

Debates

• Is P = NP for graph problems?One view: Many graph problems are known to be NP-complete, implying P != NP, meaning no efficient algorithm exists for all instances. · Another: Breakthroughs in algorithms or computational models could one day reveal efficient solutions for all NP-complete graph problems, implying P = NP.Open question
• What is the role of computational proofs in graph theory?One view: Computer-assisted proofs are valid and necessary for complex problems, extending human capabilities to verify vast numbers of cases. · Another: Proofs should ideally be verifiable by humans without computational aid to ensure deeper understanding and avoid potential software errors.Open question

Glossary

• GraphA collection of points (vertices) connected by lines (edges).
• Vertex (Node)A fundamental unit or point within a graph.
• Edge (Link)A connection between two vertices in a graph.
• DegreeThe number of edges connected to a single vertex.
• PathA sequence of distinct vertices connected by edges.
• CycleA path that starts and ends at the same vertex, with no repeated edges.

Careers

Roles this can lead toward

Student research

Published policy papers by One Young India delegates — every delegate leaves published under their own name.

• Analysing the Riemann Hypothesis and the approach to solve it through Zeta Function Analysis and Quantum-Inspired Random Matrix TheoryArnav Dhiman

Threads 13

Where this connects to other fields — and why it's worth knowing.

• Empires & Imperial Power History

  Ancient empires were basically a race against messenger speed. If an order from the capital took longer to arrive than a rebellion took to erupt, the far edges spun out of control. So the maximum size of an empire was set by one number: how many days it took news to cross the network before authority went stale.

• Rivers, Watersheds, and Water Systems Geography

  Look at a river system from above, the veins in your hand, and a lightning bolt, and they branch in eerily similar patterns. That's not a coincidence. Each one is nature's cheapest way to funnel stuff, water, blood, electric charge, from a whole spread-out area down to a single point, using the least energy possible.

• Political Economy Politics

  Draw a map of which companies own shares of which other companies, and it doesn't spread out evenly, it collapses into a tiny tangled core. One study found just 147 firms secretly control 40% of the world's corporate value through these ownership webs. Real economic power isn't on any org chart; it's a hidden pattern in the network.

• Kinship & Family Sociology

  Aboriginal Australian communities have strict rules about who can marry whom, passed down for thousands of years. When mathematicians wrote those rules out, they matched a 'group' exactly, the same math structure that describes rotating a cube. Nobody designed it that way on purpose, yet the family system runs on flawless algebra.

• Immigration & Border Policy Politics

  Once a few people from one village settle in a new country, they make it cheaper and less scary for their neighbors to follow, texting back tips, jobs, and a couch to crash on. So migration feeds itself and keeps going long after the first reason to leave is gone. That's why migrants cluster by hometown; it's chains of connections, not a random flood.

• Globalisation History

  You'd think hooking the whole world tightly together makes it sturdier. It does the opposite. In a densely linked financial network, one bank's collapse yanks on everyone wired to it, so a single local default can cascade into a worldwide crash. Tight connection spreads the damage instead of cushioning it.

• Cybercrime Law Law

  You can't chase an online hacker across a map, because they could be anywhere. Instead police trace the connections: which computers talked to which, which crypto wallets link up, what infrastructure they share. Catching them becomes less about geography and more about following the web of links.

• Pandemics Science

  A disease doesn't spread evenly, one person to the next. A few super-connected people (a nurse, a party host) infect huge numbers, while most infect almost no one. That's why the smart move is targeting those hubs, not vaccinating random people, and why one 'average' spread number hides what really matters.

• English as a Global Language Literature

  Every new person who learns English makes English more useful for everyone else to learn. That snowball locks it in as the world's default, even if another language might be 'better,' just like we're all stuck with the awkward QWERTY keyboard.

• Education and Social Mobility Sociology

  A researcher found that most people get their jobs not from close friends, but from people they barely know, a cousin's coworker, an old classmate. Those loose 'weak' connections reach into worlds your inner circle can't. So climbing in life runs a lot on the shape of your network, not just your grades.

• Cryptocurrency & Digital Money Economics

  People think Bitcoin is anonymous. Actually every transaction is written on a permanent public list anyone can read, and "chain analysis" experts routinely trace it back to real people. It's one of the least private kinds of money ever invented.

• Chokepoints & Strategic Waterways Geography

  Draw the world as dots and lines, and some lines carry a huge share of all the traffic. Cut one, and the whole map splits into disconnected pieces. Math can spot those weak links in advance, which is why the narrow Strait of Hormuz is dangerous on paper before any navy shows up.

• The Loneliness Epidemic Sociology

  Loneliness can ripple through a friend group up to three people away, like catching a cold you never touched. And it tends to push lonely people out toward the ragged edges of the network. An emotion is spreading with a shape and a pattern, like a contagion.