Graphs: connectivity, extremal edges, planarity
A graph on vertices with components and no cycle has exactly edges. So a connected graph needs at least edges, a graph with more than edges has a cycle, and a connected graph with exactly edges is a tree.
This single count replaces a surprising number of ad hoc arguments: "the process must stop" becomes "a forest cannot have edges", and "some two of these paths meet" becomes a cycle count. Two more facts earn their keep: every graph with all degrees contains a cycle (walk until you repeat a vertex), and a connected graph has a spanning tree, which gives an induction scaffold for almost any statement about connected graphs.
Triangle-free on vertices: at most edges (Mantel), attained by the balanced complete bipartite graph. No : at most edges (Turán), attained by the balanced complete -partite graph.
On vertices the triangle-free maximum is ; on vertices the -free maximum is , achieved by . Both bounds come with a construction, and an olympiad answer needs both halves: the inequality, and the example that meets it.
For a connected planar graph, . Every face of a simple planar graph with touches at least three edges, so ; if the graph is also bipartite (no triangles), .
These bounds are how non-planarity is proved without any topology: has edges, and has . A planar graph on vertices has at most edges, and a triangulation attaining it has faces. Euler also bounds degrees: every planar graph has a vertex of degree at most , which starts most planar induction proofs.
A bipartite graph with parts , has a matching saturating iff every satisfies .
Hall turns "a system of distinct representatives exists" into a condition you can check by counting neighbours, and the FAILING direction is what olympiad problems exploit: if no matching exists, some set has too few neighbours, and that deficient set is usually the structure the problem is really about. The regular case is the useful corollary: a -regular bipartite graph has a perfect matching, so its edges split into perfect matchings.
Strong induction assumes the statement for ALL smaller cases, which is what you need whenever the object splits into two smaller pieces of unpredictable size (a graph into components, a set into halves, a game into sub-games). Constructive induction goes further: guess the statement with an unknown constant, run the induction, and let the inductive step tell you which constant makes it close.
Hall's condition must hold for EVERY subset, not just single vertices. Take , with adjacent only to and adjacent to all of . Every vertex of has a neighbour, and , yet there is no matching saturating : the pair has , and . Deficient sets are usually small and structured; look for them before trusting a degree count.
What is the largest number of edges in a triangle-free graph on vertices?
Show the answerHide the answer
, attained by — five vertices on each side, all cross edges, and no triangle because any three vertices include two on the same side.
Set systems and the probabilistic method
An antichain of subsets of an -set has at most members (Sperner). The LYM inequality sharpens it: for every antichain .
LYM is proved by counting the maximal chains: each lies on of them and no chain can meet two members of an antichain. For the bound is , achieved by all -element subsets. The same chain-counting idea proves Dilworth-flavoured statements and bounds families with forbidden containments.
If finitely many convex sets in the plane have the property that every three of them share a point, then all of them share a point. In , "every " suffices.
Helly converts a global claim ("some point is in all of them") into a local one you can actually check, and the convexity hypothesis is exactly what makes the induction work. Typical use: intervals on a line (, "every two overlap" gives a common point) is the pigeonhole behind scheduling and covering problems; in the plane it handles discs, strips and half-planes.
To prove an object exists, put a probability distribution on candidates and show the bad event has probability less than , or that the expected value of some count is small enough that some outcome beats the average.
Colour the edges of at random: each of the triangles is monochromatic with probability , so the expected number of monochromatic triangles is — hence some colouring has at most . The same computation on with produces a colouring with NO monochromatic , which is Erdős's bound : an existence proof that names no colouring at all. Linearity of expectation is the whole engine, and it never needs independence.
Most olympiad "probabilistic" arguments are really the pigeonhole in disguise: some term is at least the average, some term is at most the average. Write the sum, divide by the number of terms, and pick the extreme one — no probability language needed, though the language often makes it shorter.
Helly in the plane needs every THREE sets to meet; “every two” is not enough. The three sides of a triangle, as segments, are convex and meet pairwise (at the vertices), but no point lies on all three. In the number is and it cannot be lowered — and convexity cannot be dropped either: two disjoint intervals together form a non-convex set that meets each of two others without the three sharing a point.
Proofs & Why It Matters
A triangle-free graph on vertices has at most edges.
For an edge , no vertex is adjacent to both and , so . Sum over all edges: . Cauchy–Schwarz gives , i.e. , so . Equality forces every edge to have and all degrees equal, which is the balanced complete bipartite graph.
For an antichain of subsets of , .
Count maximal chains : there are of them, and exactly pass through a given . No chain passes through two members of an antichain, so , which is the claim after dividing by . Since , it follows that .