Discrete Structures & Optimisation

Sets, relations, logic & proof

A proposition is a declarative statement that is either true or false, never both. Compound propositions are built with negation, conjunction, disjunction, implication, and biconditional. Implication deserves special care: p implies q is false only when p is true and q is false; in all other cases it is true. Its contrapositive, not q implies not p, is logically equivalent to it, while its converse, q implies p, and its inverse, not p implies not q, are not. A tautology is always true, a contradiction always false, and a contingency is sometimes true. Two formulas are equivalent when they have identical truth-table columns. De Morgan laws, distributive laws, and absorption laws let you simplify formulas, and a formula in disjunctive normal form is a disjunction of conjunctions of literals, while conjunctive normal form is the dual.

Predicate logic adds predicates, variables, and quantifiers. The universal quantifier states that a property holds for every element of a domain, and the existential quantifier states that it holds for at least one element. Order matters: for every x there exists y such that x is less than y is true over the integers, but for every y there exists x with the same property reversed is a different claim. Negating a quantified statement swaps the quantifier and negates the predicate, so the negation of for all x, P(x) is there exists x, not P(x). Arguments are tested by inference rules: modus ponens, modus tollens, hypothetical syllogism, disjunctive syllogism, addition, simplification, and conjunction. An argument is valid when the conclusion must be true whenever all premises are true; validity is not the same as the premises being true in fact.

A set is a collection of distinct objects. Subset, union, intersection, difference, complement, power set, and Cartesian product are the basic operations. A relation from set A to set B is a subset of A cross B. On a single set, a relation may be reflexive (every element relates to itself), irreflexive, symmetric (a related to b implies b related to a), antisymmetric (a related to b and b related to a implies a equals b), or transitive (a related to b and b related to c implies a related to c). An equivalence relation is reflexive, symmetric, and transitive; it partitions the set into disjoint equivalence classes whose union is the whole set, as with congruence modulo n. A partial order is reflexive, antisymmetric, and transitive; its Hasse diagram draws only the covering relations, omitting reflexive loops and transitive edges. The reflexive, symmetric, or transitive closure of a relation is the smallest relation with that property containing the original.

A function f from A to B assigns each element of A exactly one element of B. It is injective (one-to-one) when distinct inputs give distinct outputs, surjective (onto) when every element of B is hit, and bijective when both hold. Composition applies one function after another, and only bijective functions have two-sided inverses. Proof methods build on this foundation. A direct proof assumes the hypothesis and derives the conclusion. Proof by contraposition proves the contrapositive instead. Proof by contradiction assumes the negation of the conclusion and derives an absurdity. Mathematical induction proves a statement P(n) for all natural numbers n by a base case, usually n equals 0 or 1, and an inductive step showing P(k) implies P(k plus 1). Strong induction allows assuming P for all values up to k. Examinations test induction most often on sums, divisibility, and inequalities, and the common failure is a weak inductive step that assumes what must be proved.

Graphs & trees

A graph consists of vertices and edges joining pairs of vertices. In a simple graph there are no loops and no multiple edges. The degree of a vertex is the number of incident edges, with a loop contributing two. The handshaking lemma states that the sum of all degrees equals twice the number of edges, so the number of vertices of odd degree is always even. A path is a sequence of vertices with consecutive pairs joined by edges and no repeated vertex except possibly the endpoints; a cycle is a closed path. A graph is connected when there is a path between every pair of vertices, and a complete graph on n vertices has every pair joined. A bipartite graph has its vertices split into two sets with edges only between sets, never within one set. Two graphs are isomorphic when there is a bijection between their vertex sets preserving adjacency exactly; equal numbers of vertices, edges, and degree sequences are necessary but not sufficient for isomorphism, so a claimed isomorphism must be checked edge by edge.

An Euler path uses every edge exactly once, and an Euler circuit returns to its start. A connected graph has an Euler circuit exactly when every vertex has even degree, and an Euler trail between two distinct vertices exactly when exactly two vertices have odd degree, which must then be the endpoints. A Hamiltonian path visits every vertex exactly once, and a Hamiltonian cycle returns to the start; unlike the Euler case there is no simple necessary and sufficient degree condition, so Hamiltonian questions are usually solved by construction, by exhibiting a cycle, or by a contradiction argument showing no cycle can exist. A planar graph can be drawn in the plane without edge crossings. For a connected planar graph with v vertices, e edges, and f faces, Euler formula gives v minus e plus f equals 2. For a simple planar graph with at least three vertices, e is at most 3v minus 6, and if it is also triangle-free, e is at most 2v minus 4; violating such a bound proves non-planarity. The complete graph K5 and the complete bipartite graph K3,3 are the classic non-planar obstructions.

Graph colouring assigns colours to vertices so adjacent vertices differ. The chromatic number is the smallest number of colours needed. A bipartite graph needs at most two colours, an odd cycle needs three, and the four-colour theorem says every planar graph needs at most four. Greedy colouring in a bad vertex order can use more colours than optimal, so greedy output is an upper bound, not the chromatic number. A tree is a connected acyclic graph. A tree with n vertices has exactly n minus 1 edges, has a unique simple path between any two vertices, and becomes cyclic if any edge is added or disconnected if any edge is removed. A spanning tree of a connected graph is a tree using all its vertices and a subset of its edges. A minimum spanning tree minimises total edge weight. Kruskal algorithm sorts edges by weight and adds an edge unless it creates a cycle, while Prim algorithm grows a tree from a starting vertex by repeatedly adding the cheapest edge to a new vertex. Both are greedy and both are correct for minimum spanning trees, with running time dominated by sorting or by priority-queue operations. Rooted trees model hierarchies and expression evaluation: binary trees, traversal orders (preorder, inorder, postorder), and binary search tree properties are examined through small worked trees rather than large ones.

Combinatorics & probability

Counting begins with two rules. The product rule multiplies the numbers of independent choices, and the sum rule adds the numbers of mutually exclusive cases. A permutation counts arrangements where order matters: the number of permutations of n distinct objects taken r at a time is n factorial divided by (n minus r) factorial. A combination counts selections where order does not matter: n choose r equals n factorial divided by r factorial times (n minus r) factorial, and n choose r equals n choose (n minus r). Permutations with repetitions, permutations of multiset objects, and combinations with repetition each have their own formula, and the examination trap is choosing the wrong model, for example counting ordered selections when the problem asks for committees. The binomial theorem expands (x plus y) to the power n as a sum of terms with binomial coefficients, and Pascal identity builds the coefficients recursively.

The pigeonhole principle states that if more than n objects are placed into n boxes, some box holds at least two objects. Its generalised form says that placing N objects into n boxes forces some box to hold at least the ceiling of N divided by n objects. This principle proves existence without construction, for instance that among a group of people two share a birth month, or that a sequence of numbers contains a repeated remainder. Inclusion-exclusion corrects overcounting when sets overlap: the size of the union of two sets equals the sum of their sizes minus the size of their intersection, and the three-set formula adds back the triple intersection after subtracting pairwise intersections. It is the standard tool for counting onto functions, derangements, and numbers coprime to a given integer.

A recurrence relation defines a sequence term from earlier terms, together with initial conditions. The Fibonacci recurrence, Tower of Hanoi recurrence, and divide-and-conquer recurrences such as T(n) equals 2 T(n over 2) plus n are standard. Linear homogeneous recurrences with constant coefficients are solved by the characteristic equation: assume a solution of the form r to the power n, solve for r, and combine roots, multiplying by n for repeated roots. Non-homogeneous recurrences add a particular solution matched to the forcing term. Generating functions offer an alternative route but are rarely needed beyond recognition. In probability, the sample space lists all outcomes, an event is a subset of it, and probability is the ratio of favourable to total outcomes in an equally likely model. Conditional probability, independence, Bayes theorem, expectation, and variance are examined through small discrete examples: dice, cards, urns, and coin tosses. Remember that independent events satisfy P(A and B) equals P(A) times P(B), while mutually exclusive events satisfy P(A or B) equals P(A) plus P(B); the two concepts are different and are frequently confused.

Linear programming & optimisation

A linear program optimises a linear objective function subject to linear constraints and non-negativity conditions. Decision variables are the quantities to choose, the objective states profit or cost to maximise or minimise, and constraints encode limited resources, demands, or capacities. A feasible solution satisfies all constraints, the feasible region is the set of all feasible solutions, and an optimal solution is a feasible solution with the best objective value. The fundamental theorem of linear programming says that if an optimal solution exists, one occurs at a corner point, or vertex, of the feasible region, provided the region is a convex polyhedron. This is why the graphical method works for two variables: draw each constraint as a line, shade the feasible region, evaluate the objective at each corner, and pick the best value, checking also for unboundedness and infeasibility when the region is empty or open in the improving direction.

The simplex method generalises the graphical idea to many variables. It starts at a corner point, expressed as a basic feasible solution in a tableau, and moves along an edge to a neighbouring corner that improves the objective, repeating until no improving move exists. Slack variables convert less-than-or-equal constraints into equations, surplus variables handle greater-than-or-equal constraints, and artificial variables with the Big-M method or the two-phase method handle equalities and greater-than constraints. Degeneracy, when a basic variable equals zero, can cause cycling in theory, though examinations usually test one or two tableau steps, pivot choice, and the optimality condition rather than full cycling remedies. Duality pairs every primal maximisation problem with a dual minimisation problem: primal constraints become dual variables, primal variables become dual constraints, and the objective coefficients swap with the right-hand sides. Weak duality says any feasible dual value bounds the primal optimum, and strong duality says the two optima are equal when both are feasible and bounded. Complementary slackness links primal and dual optimal solutions and is a favourite short-answer topic.

The transportation problem ships goods from sources with supplies to destinations with demands at minimum cost, with total supply equal to total demand in the balanced case. An initial basic feasible solution is found by the North-West corner rule, the least-cost method, or Vogel approximation method, and optimality is tested and improved with the stepping-stone method or the MODI (modified distribution) method using dual potentials. The assignment problem is the special case with equal numbers of workers and jobs and one assignment each, solved by the Hungarian method: subtract row minima, subtract column minima, cover zeros with the minimum number of lines, and adjust uncovered elements until an assignment using only zeros exists. Unbalanced problems are balanced with dummy sources, destinations, workers, or jobs at zero cost, and prohibited assignments are handled with a very large cost. In examinations, distinguish these models by their structure: transportation allows split shipments, assignment forbids them, and both are linear programs with totally unimodular structure, so integer solutions arise naturally without integer programming.

Proof methods compared

Euler versus Hamiltonian

Relation properties at a glance