Graphs Through the Lens of Discrete Mathematics, Explained

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 17.4 Free with a free account

Graphs Through the Lens of Discrete Mathematics

Data Structures and Algorithms · Chapter 17: Graphs and MemorySection 17.4 · lesson 81 of 8714 min · free with a free account

← Cheapest Routes in a Weighted NetworkNext lesson: Telling Networks Apart by Shape, Density, and Loops →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Proving graph facts with sets, relations, degrees, and induction.

  • Describe a graph as a pair of sets and classify its adjacency and reachability relations
  • Prove and apply the handshake lemma to reject impossible degree lists
  • Decide from vertex degrees whether a graph has an Euler trail or circuit
  • Use invariants and induction correctly to reason about graphs

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (2,012 words). Read along, or search it.

Opening Question

Nine People, Five Handshakes Each

Nine people meet at a party. Can every one of them shake hands with exactly five others? You could try to draw it, adding handshakes and rubbing them out, for a long time. Or you could answer in one line, without drawing anything. This lesson is about that kind of answer: what can be proved about a graph without running any search at all.

Formal Definition

A Graph as a Pair of Sets

In discrete mathematics, the picture is set aside. A graph is a pair, G equals V and E. V is a finite set of vertices, and E is a set of two-element subsets of V, one for each edge. Nothing else is needed. Every question about a graph is a question about those two sets. The graph also gives a relation, R: u is adjacent to v. Each edge u, v produces two ordered pairs, u v and v u, so five edges give ten pairs. And the adjacency matrix is simply the table of that relation: row u, column v holds true when the pair is in R.

Relation Properties

Irreflexive and Symmetric but Not Transitive

A relation can have four classic properties. Reflexive: every vertex is related to itself. Irreflexive: none is. Symmetric: u related to v forces v related to u. And transitive: u to v, and v to w, force u to w. The adjacency relation of a simple graph is irreflexive, since no edge joins a vertex to itself, and symmetric, since an edge has no direction. But it isn't transitive. Zero is adjacent to two, and two to three, yet zero isn't adjacent to three. In fact it can never be, unless there are no edges at all. Symmetry turns u v into v u, transitivity would then force u u, and irreflexive forbids that. Of all thirty-two thousand, seven hundred sixty-eight graphs on six vertices, only the empty one is transitive.

Equivalence Relation

Reachability Groups Vertices Into Components

Transitivity is what reachability adds. Say v is reachable from u when a path leads from u to v, and let every vertex reach itself. That relation is reflexive, because a path may have no edges. It's symmetric, because a path can be walked backward. And it's transitive, because two paths can be joined. A relation with all three properties is an equivalence relation, and it splits the vertices into groups. Here the groups are exactly the connected components: zero, one, two, three, and four, five. Matrices count more than that. Squaring the adjacency matrix counts walks of two edges: the entry for zero, three is one, the walk zero, two, three.

Handshake Lemma

Counting One Set in Two Ways

Now the most useful fact in all of graph theory. The handshake lemma: in every graph, the degrees add up to twice the number of edges. The proof counts one set in two ways. Count the pairs: a vertex, and an edge it belongs to. Every edge has exactly two ends, so there are two times E such pairs. Every vertex v appears in exactly degree of v of them, so there are also the sum of the degrees. Two counts of one set must agree. Back to the party. Nine people with five handshakes each would give a degree sum of forty-five. That's odd, and twice anything is even. So it's impossible, without drawing a single line.

Consequences

Odd-Degree Vertices Come in Even Numbers

Two consequences follow at once. First, the number of odd-degree vertices is always even. The degree sum is even, so the odd degrees must add to an even number, which needs an even count of them. Second, edge counts follow from degrees. In the complete graph on n vertices, every degree is n minus one, so there are n times n minus one, over two, edges. If every degree is k, there are n k over two edges, so n times k must be even. A graph where every vertex has degree three needs an even number of vertices. With five vertices, there's none. For directed graphs the rule is even simpler. Every edge leaves one vertex and enters one, so the out-degrees and the in-degrees each add up to E.

Limits of Parity

An Even Sum Does Not Guarantee a Graph

But the lemma only works one way. A list of degrees must have an even sum, yet an even sum doesn't promise that a graph exists. Take three, three, one, one. The sum is eight, which is even. But the two vertices of degree three must each be joined to all three others. Then each of the remaining two vertices already has two neighbors, so neither can have degree one. No graph has that list. On four vertices, nineteen lists of degrees have an even sum, and only eleven of them belong to a real graph. Parity can reject a list. It can never accept one.

Quick Check

The Degree List Three, Three, Three, One

Quick check. A designer asks for a network of four computers, where three of them each have three cables, and the fourth has one. The degree list is three, three, three, one. Is it possible because the sum is even, impossible because the sum is odd, or impossible despite an even sum? Pause, and decide. Impossible, despite an even sum. Three plus three plus three plus one is ten, so parity is no objection. But with four vertices, a degree of three means being joined to all three others. Three such vertices would each be joined to the fourth, giving it degree three, not one.

Euler Trails

The Seven Bridges of Konigsberg

A walk that never repeats an edge is called a trail. An Euler trail uses every edge exactly once, and an Euler circuit is an Euler trail that ends where it began. The first such question was asked about the city of Konigsberg: could a walk cross each of its seven bridges exactly once? As a graph, the two river banks, the island, and the east side are vertices, and the seven bridges are edges, some of them parallel. The degrees are three, three, five, and three. Four odd vertices. And that settles it: no such walk exists, as the next rule shows.

Euler's Rule

Even Degrees and Hierholzer's Splicing

Euler's rule, for a graph whose edges are all in one connected piece: an Euler circuit exists exactly when every degree is even. And an Euler trail exists exactly when there are zero or two odd vertices. With two, the trail must start at one and end at the other. Why even? A walk passing through a vertex arrives on one edge and leaves on another, so it uses the edges there in pairs. In a circuit, that holds everywhere, even at the start. Why is even enough? Start anywhere and keep walking on unused edges. You can only get stuck back at the start, which closes a circuit. Leftover edges form more circuits that splice in. That splicing is Hierholzer's algorithm. Add one bridge to Konigsberg, and two vertices become even: an Euler trail appears, starting and ending at the two odd ones. Add a second, and every degree is even: now there's a circuit.

Connectivity

Why the Rule Needs One Connected Piece

The rule needs that word, connected. Two separate triangles have only even degrees, every one of them two, yet no single walk can cover both. So the test is the degrees, plus one connectivity check, the kind of search from earlier lessons. Vertices with no edges don't matter, since there's nothing to cross. Checked against a brute-force search on every graph with three, four, and five vertices, the degree test never once disagreed. On five vertices, all one thousand twenty-four graphs matched.

Quick Check

Two Odd Vertices Mean a Trail

Quick check. A connected graph has the degrees four, two, two, three, three, and two. Does it have an Euler circuit, an Euler trail but no circuit, or neither? Pause, and decide. A trail, but no circuit. Exactly two vertices, the two of degree three, are odd. So any Euler trail must start at one of them, and end at the other. And the degree sum is sixteen, so the graph has eight edges.

Hamiltonian Paths

Visiting Every Vertex Exactly Once

A Hamiltonian path visits every vertex exactly once, and a Hamiltonian cycle can return to its start along an edge. It sounds like Euler's question, and it isn't. Euler cares about edges, and has a one-line test. Hamilton cares about vertices, and has no known test that's both simple and complete. The bowtie has an Euler circuit, since every degree is even, but no Hamiltonian cycle: the middle vertex would have to be visited twice. K four is the other way around. Every degree is three, so there's no Euler circuit, but a Hamiltonian cycle goes round all four corners.

Dirac's Condition

A One-Way Guarantee and Backtracking

Some conditions do guarantee a Hamiltonian cycle. The best known is Dirac's: with at least three vertices, if every degree is at least half the number of vertices, a Hamiltonian cycle exists. But it's a one-way street. When it fails, nothing is decided. The six-cycle has every degree two, below six over two, and yet it's its own Hamiltonian cycle. Without a test, the fallback is backtracking: extend a path one vertex at a time, and undo the last step when stuck. When the answer is no, the search must try everything before giving up. On complete bipartite graphs with no Hamiltonian path, adding two vertices multiplied the work by fifteen, then twenty-four, thirty-five, forty-eight, and sixty-three. Going from fourteen to sixteen vertices turned under two seconds into about two minutes. Look for an argument before running the search.

Isomorphism

Invariants Can Only Reject

Two drawings can look different, and still be the same graph with the vertices renamed. Graphs are isomorphic when some renaming maps edges to edges exactly: none lost, and none added. To prove two graphs are isomorphic, give the renaming, and check every edge. To prove they aren't, trying renamings by hand is hopeless, so use an invariant: a quantity no renaming can change. The six-cycle and two separate triangles have the same six vertices, the same six edges, and the same degree list, all twos. But one is connected and the other isn't, so they're different graphs. Invariants can only reject. Equal invariants never prove two graphs are the same. On six vertices, eighty-four of the hundred fifty-six different shapes share their degree list with another shape. And trying every renaming costs n factorial: seven hundred twenty for six vertices, over one point three trillion for fifteen.

Induction

Remove a Piece and Put It Back

The last tool is induction. Show a statement for the smallest graph, the base case. Then show that if it holds for size n, it holds for size n plus one. For graphs, the step usually has one shape: take the bigger graph, remove one piece, apply the hypothesis to what's left, and put the piece back. Claim: the complete graph on n vertices has n times n minus one, over two, edges. Take the complete graph on n plus one vertices, and remove one vertex. What's left is the complete graph on n vertices. The removed vertex carried n edges, and adding them back gives the formula for n plus one. Claim: a tree with n vertices has n minus one edges. Every tree with two or more vertices has a leaf. Remove a leaf and its one edge, and what's left is still a tree, so the count works out.

Common Mistake

When the Smaller Graph Leaves the Family

One rule makes or breaks the proof: the smaller graph must still belong to the family the hypothesis talks about. Here's a false claim. Every graph in which each vertex has at least one neighbor is connected. A tempting proof removes a vertex, and applies the hypothesis to the rest. It breaks at once. Take two separate edges: zero, three, and one, two. Remove vertex zero, and vertex three loses its only neighbor. The smaller graph has left the family, so the hypothesis says nothing about it. And the claim is simply false: the two separate edges are the counterexample.

Key Takeaways

Graph Proofs in Brief

To sum up. A graph is a pair of sets. Its adjacency relation is symmetric and irreflexive, and reachability, an equivalence relation, groups it into components. The degrees add up to twice the edges, which can reject a degree list, but never confirm one. Euler circuits need every degree even, and trails need zero or two odd vertices. Hamiltonian paths have no simple test. Invariants can show two graphs differ. And an induction step must leave the smaller graph inside its family.

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Graphs Through the Lens of Discrete Mathematics

What is the handshake lemma?
The handshake lemma states that in every graph the vertex degrees add up to twice the number of edges. The proof counts vertex-edge pairs two ways: each edge has two ends, giving 2E pairs, and each vertex v appears in deg(v) of them. It follows that the number of odd-degree vertices is even, so nine people cannot each shake exactly five hands, since 45 is odd.
When does a graph have an Euler circuit or an Euler trail?
A graph whose edges lie in one connected piece has an Euler circuit exactly when every vertex degree is even, and an Euler trail exactly when it has zero or two odd-degree vertices. With two, the trail starts at one odd vertex and ends at the other. The Königsberg bridge graph has degrees 3, 3, 5, and 3, four odd vertices, so no walk crosses each bridge exactly once.
What is the difference between an Euler path and a Hamiltonian path?
An Euler path uses every edge exactly once, while a Hamiltonian path visits every vertex exactly once. Euler paths have a simple degree test, but Hamiltonian paths have no known test that is both simple and complete. The bowtie graph has an Euler circuit but no Hamiltonian cycle, while the complete graph K4 has a Hamiltonian cycle but no Euler circuit, since every vertex has degree three.
How do you prove two graphs are not isomorphic?
To prove two graphs are not isomorphic, find an invariant, a property no renaming of the vertices can change, on which they differ. A six-cycle and two separate triangles share six vertices, six edges, and a degree list of all twos, but one is connected and the other is not, so they differ. Equal invariants never prove sameness; that requires a renaming that maps every edge to an edge.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →