Graph theory

يعتمد على

عدد المتطلبات السابقة الإلزامية (حتى الأساس): 18

ستتعلّم

• Prove Hall's marriage theorem and apply it.
• Prove Euler's formula V − E + F = 2 for connected plane graphs and deduce that K₅ and K₃,₃ are not planar.
• Prove that R(3, 3) = 6 and establish upper bounds for Ramsey numbers.

تعريف

• A matching is a set of edges no two of which share a vertex.
• A proper k-colouring assigns one of k colours to each vertex so that adjacent vertices receive different colours.
• The Ramsey number R(s, t) is the least n such that every red–blue colouring of the edges of Kₙ contains a red K_s or a blue K_t.

مبرهنة

• Hall: a bipartite graph with parts A and B has a matching covering A if and only if |N(S)| ≥ |S| for every S ⊆ A.
• Four colour theorem (Appel and Haken, 1976): every planar graph is 4-colourable; the proof relies on computer verification.
• Kuratowski: a graph is planar if and only if it contains no subdivision of K₅ or K₃,₃.
• R(3, 3) = 6.

مفاهيم خاطئة شائعة

• Thinking a graph is planar only if a given drawing has no crossings; it is planar if some drawing has none.
• Assuming the four colour theorem has a short proof checkable by hand; known proofs use computers, and one has been formally verified in Coq.

يقود إلى

اكتشافات اختيارية

• Computational complexity Deciding whether a graph is 3-colourable is NP-complete.
• ← Algorithm design and analysis

مسارات التعلّم

• Undergraduate mathematics major

قراءات إضافية

• Reinhard Diestel, Graph Theory
• J. A. Bondy and U. S. R. Murty, Graph Theory with Applications (1976)