• ES Español (Latinoamérica)
• EN English

4.7. Discrete Mathematics and Combinatorics (DMC)

This area covers the mathematics of finite and countable structures, including combinatorial enumeration, graph theory, discrete optimization, and the logical foundations of mathematics. It underpins theoretical computer science, operations research, and modern data science.

Knowledge Area (KA)	Core Tier1	Core Tier2
4.7.1 Graph Theory	1	1

4.7.1. DMC/Graph Theory  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Back to top

Structure and properties of graphs: connectivity, colorings, matchings, planarity, and spectral graph theory.
Topics:
Core

• Graphs: definitions, isomorphism, degree sequences, trees, and spanning trees
• Connectivity, Menger's theorem, and network flows (max-flow min-cut)
• Matchings (Hall's theorem), graph colorings, and the chromatic polynomial
• Planar graphs, Euler's formula, Kuratowski's theorem, and the four-color theorem
• Adjacency and Laplacian matrices, eigenvalues, and expander graphs

Learning Outcomes:
Core:

1. Identify structural properties of graphs (connectivity, planarity, bipartiteness) and apply Euler's formula [Familiarity]
2. Apply Hall's marriage theorem and network flow algorithms to matching and routing problems [Usage]
3. Analyze a graph's spectrum to bound its chromatic number and connectivity properties [Assessment]