Engineering Mathematics · topic
Degrees and the handshake lemma, connectivity, components, cut vertices and bridges, edge bounds; Euler and Hamilton graphs, bipartite graphs, planar graphs and Euler's formula; matching and Hall's theorem, independence and covering numbers, vertex and edge colouring and chromatic number bounds.
A graph models objects and pairwise connections between them: computers and links, cities and roads, tasks and conflicts, states and transitions. Graph theory supplies the vocabulary (degree, path, cycle, tree, planar) and the counting facts used in connectivity, matching and colouring.
A network is useful only if its parts can reach each other, and it is robust only if it stays connected when something fails.
A matching pairs up vertices along edges so that no vertex is used twice: assigning workers to jobs they are qualified for, students to projects, or tasks to processors.
Colouring a graph means giving each vertex a colour so that adjacent vertices get different colours.
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
