HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
  1. Notes
  2. /Graph Theory: Quick Revision
Mathematics

Graph Theory: Quick Revision

A brief note on graph theory: degrees and the handshake lemma, trees, bipartite graphs, Euler trails, planar graphs and Euler's formula, colouring and Ramsey numbers. With practice, a program and questions to check yourself.

StemPy LabWritten by StemPy Lab
Log in to save

A brief note on Graph Theory. Read it before a test. Try each question at the end before you open its answer.

Degrees

  • Handshake lemma: ∑deg⁡v=2E\displaystyle\sum \deg v = 2E∑degv=2E; the number of odd vertices is even.
  • Complete graph: KnK_nKn​ has (n2)\dbinom{n}{2}(2n​) edges.
  • Two equal degrees in every simple graph with at least two vertices.
  • Connected for sure: more than (n−12)\dbinom{n - 1}{2}(2n−1​) edges.
  • Havel–Hakimi: remove the largest degree ddd and subtract 111 from the next ddd.

Trees, bipartite graphs, Euler

  • Tree: connected, no cycle, n−1n - 1n−1 edges, at least two leaves; forest with ccc trees: n−cn - cn−c edges.
  • Cayley: nn−2n^{n-2}nn−2 labelled trees.
  • Bipartite: no odd cycle. Km,nK_{m,n}Km,n​ has mnmnmn edges.
  • Mantel: no triangle, at most n24\dfrac{n^2}{4}4n2​ edges.
  • Euler circuit: connected, all degrees even. Euler trail: exactly two odd vertices.

Planar graphs, colouring, Ramsey

  • Euler's formula: V−E+F=2V - E + F = 2V−E+F=2.
  • Edge bounds: E≤3V−6E \le 3V - 6E≤3V−6; no triangle: E≤2V−4E \le 2V - 4E≤2V−4. K5K_5K5​ and K3,3K_{3,3}K3,3​ are not planar.
  • Colouring: χ(Kn)=n\chi(K_n) = nχ(Kn​)=n; bipartite means χ≤2\chi \le 2χ≤2; odd cycle needs 333; χ≤Δ+1\chi \le \Delta + 1χ≤Δ+1; planar graphs need at most 444.
  • Ramsey: R(3,3)=6R(3, 3) = 6R(3,3)=6, R(3,3,3)=17R(3, 3, 3) = 17R(3,3,3)=17.

A worked example

A connected planar graph has 999 vertices and 151515 edges. How many faces?

  1. Formula. V−E+F=2V - E + F = 2V−E+F=2.
  2. Substitute. 9−15+F=29 - 15 + F = 29−15+F=2.
  3. Answer. F=8F = 8F=8.

Practice with new numbers

A program to try

The program checks three facts by trying every case.

Read it first. Then run it. Does the count of trees agree with Cayley's formula?

1. Change the first part to trees on 444 vertices. Predict the count with nn−2n^{n-2}nn−2 first.

Mistakes to avoid

  • Halving forgotten in the handshake lemma.
  • The outside face left out of FFF.
  • Euler and Hamilton mixed up.
  • A forest treated as a tree.
  • An even degree sum taken as proof that a graph exists.

Check yourself

  1. How many edges does K7K_7K7​ have?
  1. Can a graph have degrees 3,3,3,2,23, 3, 3, 2, 23,3,3,2,2?
  1. A tree has 999 edges. How many vertices?
  1. Does K2,4K_{2,4}K2,4​ have an Euler circuit?
  1. What is χ\chiχ of a cycle with 888 vertices?

Sources

  • D. B. West, Introduction to Graph Theory, Chapters 1, 2, 5 and 6.
  • R. J. Wilson, Introduction to Graph Theory.
← All Notes
← Recurrences and Counting by Recursion: Quick RevisionCeva, Menelaus and Triangle Centres: Quick Revision →
More onPigeonhole Principle, Recursion and Graph Theory

Discussion (0)

Log in to join the discussion.

Loading…

On this page

  1. Degrees
  2. Trees, bipartite graphs, Euler
  3. Planar graphs, colouring, Ramsey
  4. A worked example
  5. Practice with new numbers
  6. A program to try
  7. Mistakes to avoid
  8. Check yourself
  9. Sources

Goes with the lesson

  1. Planar graphs, colouring and Ramsey numbersGraph Theory

More notes on this topic

  1. Recurrences and Counting by Recursion: Quick Revision
  2. The Pigeonhole Principle: Quick Revision
All notes on this topic →