Combinatorics and Graph Theory

by David Guichard

Read here Read at LibreTextsPDF

Combinatorics is often described briefly as being about counting, and indeed counting is a large part of combinatorics.Graph theory is concerned with various types of networks, or really models of networks called graphs. These are not the graphs of analytic geometry, but what are often described as "points connected by lines''.

Description from LibreTexts.

Publisher
Whitman College
Subjects
Mathematics, Combinatorics and Discrete Mathematics
Licence
CC BY-NC-SA 4.0, as LibreTexts states it. Non-commercial use only.
Who can read
Tweens profiles and older, judged from its title and subjects

Contents

LibreTexts writes equations in TeX, and here they show as TeX; the PDF has them typeset.

  1. Front Matter
  2. TitlePage
  3. InfoPage
  4. Table of Contents
  5. Licensing
  6. 1: Fundamentals
  7. 1.1: Prelude to Fundamentals
  8. 1.2: Examples
  9. 1.3: Combinations and Permutations
  10. 1.4: Binomial Coefficients
  11. 1.5: Bell Numbers
  12. 1.6: Choice with Repetition
  13. 1.7: The Pigeonhole Principle
  14. 1.8: Sperner's Theorem
  15. 1.9: Stirling numbers
  16. 1.E: Fundamentals (Exercises)
  17. 2: Inclusion-Exclusion
  18. 2.1: The Inclusion-Exclusion Formula
  19. 2.2: Forbidden Position Permutations
  20. 2.E: Inclusion-Exclusion (Exercises)
  21. 3: Generating Functions
  22. 3.1: Prelude to Generating Functions
  23. 3.2: Newton's Binomial Theorem
  24. 3.3: Exponential Generating Functions
  25. 3.4: Partitions of Integers
  26. 3.5: Recurrence Relations
  27. 3.6: Catalan Numbers
  28. 3.E: Generating Functions (Exercises)
  29. 4: Systems of Distinct Representatives
  30. 4.1: Prelude to Systems of Distinct Representatives
  31. 4.2: Existence of SDRs
  32. 4.3: Partial SDRs
  33. 4.4: Latin Squares
  34. 4.5: Introduction to Graph Theory
  35. 4.6: Matchings
  36. 4.E: Systems of Distinct Representatives (Exercises)
  37. 5: Graph Theory
  38. 5.1: The Basics of Graph Theory
  39. 5.2: Euler Circuits and Walks
  40. 5.3: Hamilton Cycles and Paths
  41. 5.4: Bipartite Graphs
  42. 5.5: Trees
  43. 5.6: Optimal Spanning Trees
  44. 5.7: Connectivity
  45. 5.8: Graph Coloring
  46. 5.9: The Chromatic Polynomial
  47. 5.10: Coloring Planar Graphs
  48. 5.11: Directed Graphs
  49. 5.E: Graph Theory (Exercises)
  50. 6: Pólya–Redfield Counting
  51. 6.1: Prelude to Pólya–Redfield Counting
  52. 6.2: Groups of Symmetries
  53. 6.3: Burnside's Theorem
  54. 6.4: Pólya-Redfield Counting
  55. 6.E: Pólya–Redfield Counting (Exercises)
  56. Back Matter
  57. Index
  58. Glossary
  59. Detailed Licensing