GATE CS Mastery
My library

Engineering Mathematics · topic

Graph theory: connectivity, matching and colouring

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.

Cheat sheets

EM-09Cheat sheet1 pageIn a paid pack

Graphs: Degrees, Connectivity, Bounds

Walks, trails, paths and cycles, the handshake lemma and its parity consequences, graphic degree sequences and Havel-Hakimi, edge bounds for simple, connected, disconnected, k-component and bipartite graphs with the extremal graph behind each, cut vertices, bridges and blocks with a diagram, vertex and edge connectivity and Whitney's inequality, complements, trees and Cayley's formula, adjacency-matrix walk counts, isomorphism invariants and counts of labelled and unlabelled graphs.

Get the full pack
Partial preview

A partial preview of the top of the sheet. The full sheet is in the Engineering Mathematics cheat sheet pack.

Partial preview

Diagrams from EM-09

Graph on vertices 1 to 7: triangle 1-2-3, bridge 3-4, triangle 4-5-6, bridge 6-7. Vertices 3, 4 and 6 are filled as cut vertices; edges 3-4 and 6-7 are dashed as bridges.
Removing a filled vertex or a dashed edge disconnects the graph. Source: sheet EM-09.

EM-10Cheat sheet1 pageIn a paid pack

Euler, Hamilton, Bipartite, Planar

Euler circuits and trails with their degree conditions (undirected and directed), Hamiltonian cycles with Dirac's and Ore's sufficient conditions and quick necessary tests, counts of Hamiltonian cycles in complete graphs, bipartite graphs and the odd-cycle test, planar graphs with Euler's formula for connected and k-component graphs, the 3n - 6 and 2n - 4 edge bounds and why they are only necessary, K5 and K3,3, face degrees, and a diagram of a planar redrawing.

Get the full pack
Partial preview

A partial preview of the top of the sheet. The full sheet is in the Engineering Mathematics cheat sheet pack.

Partial preview

Diagrams from EM-10

Left: K4 drawn as a square with both diagonals crossing. Right: the same graph redrawn without crossings as a triangle a, b, c with vertex d inside joined to all three, showing inner faces f1, f2, f3 and the outer face f4.
Planarity is about some drawing, not the given one. Source: sheet EM-10.

EM-11Cheat sheet1 pageIn a paid pack

Matching, Covering and Colouring

Matchings (maximal, maximum, perfect), vertex covers, independent sets and edge covers with the Gallai identities and Konig's theorem, Hall's marriage condition with an example that fails it, counts of perfect matchings in complete and complete bipartite graphs, vertex colouring with clique, independence and maximum-degree bounds, Brooks and the four-colour theorem, chromatic numbers of standard graphs, edge colouring with Vizing's theorem, and chromatic polynomials, all checked on small graphs.

Get the full pack
Partial preview

A partial preview of the top of the sheet. The full sheet is in the Engineering Mathematics cheat sheet pack.

Partial preview

Diagrams from EM-11

Left: bipartite graph with x1, x2, x3 on top and y1, y2, y3 below; the perfect matching x1-y2, x2-y1, x3-y3 is bold and the other edges x1-y1 and x3-y2 are dashed. Right: a 5-cycle with vertices coloured 1, 2, 1, 2, 3.
Left: the only perfect matching (x2 can only use y1). Right: an odd cycle needs a third colour. Source: sheet EM-11.