[Submitted on 2 Aug 2023]
Download PDF
Abstract: This is a graduate-level introduction to graph theory, corresponding to a
quarter-long course. It covers simple graphs, multigraphs as well as their
directed analogues, and more restrictive classes such as tournaments, trees and
arborescences. Among the features discussed are Eulerian circuits, Hamiltonian
cycles, spanning trees, the matrix-tree and BEST theorems, proper colorings,
Turan’s theorem, bipartite matching and the Menger and Gallai–Milgram
theorems. The basics of network flows are introduced in order to prove Hall’s
marriage theorem.
Around a hundred exercises are included (without solutions).
Submission history
From: Darij Grinberg [view email]
[v1]
Wed, 2 Aug 2023 23:24:26 UTC (661 KB)
>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Hacker News – https://arxiv.org/abs/2308.04512