A tree is a nonempty connected graph with no graph cycle. A leaf of a tree is a vertex of vertex degree one. As usual in this finite graph theory problem, trees are finite; the assertion would fail for a doubly infinite graph path.
Take a longest path in a tree with at least two vertices. Connectedness gives . If had a neighbour outside this graph path, the path could be extended, contradicting maximal length. If it had a neighbour with , that edge together with the segment would make a graph cycle. Thus its only neighbour is , and it is a leaf of a tree. The same argument at the other end makes a second, distinct leaf of a tree. Hence
Ramsey number 2026-10-14
For positive integers , the Ramsey number is the least integer such that every red-blue edge coloring of the complete graph contains either a red clique on vertices or a blue clique on vertices. The complete graph has all unordered pairs as edges; every edge gets exactly one color, with no requirement that incident edges have different colors. The definition and its graph interpretation appear in D. Yogeshwaran's Discrete Mathematics notes, section 5.3.
For example, asks how many vertices force a monochromatic triangle in a graph. Swapping colors gives . Also : either a red edge exists, or all edges are blue. On vertices, an all-blue coloring avoids both a red edge and a blue -clique. Under the convention that a one-vertex clique qualifies in either color, .
For , splitting the neighbors of one vertex by the colors of their incident edges gives
Indeed, in a complete graph of the order on the right, at least neighbors are joined to that vertex by red edges, or at least are joined by blue edges. In the red case, the defining property of the smaller Ramsey number supplies either a blue -clique among the neighbors or a red -clique that extends by the chosen vertex; the blue case is symmetric. Starting from the one-vertex base cases, this recursively proves finite existence. The binomial upper bound for a Ramsey number packages the resulting estimate. [ref] present the neighbor argument and the sharp Ramsey number for triangles.
Equivalently, every graph on at least vertices has an -clique or a -element independent set: color its edges red and the edges of its complement graph blue. This is the Ramsey theorem in graph theory. Larger monochromatic patterns have their own thresholds, such as a graph Ramsey number, matching Ramsey number or triangle-packing Ramsey number; these ask different questions from finding one clique.
William Thomas Tutte Created 2026-10-24 Updated 2026-11-05