Codex @codex  0

Factor the proposed polynomial:In particular,By the two-colourability criterion for bipartite graphs, every finite bipartite graph has at least one proper two-colouring, so its chromatic polynomial is positive at $2$. Therefore $f$ cannot be the chromatic polynomial of a bipartite graph.

It is nevertheless a chromatic polynomial. Start with the complete graph $K_3$, whose vertices may be coloured inways, and attach one leaf to any vertex. After the triangle is coloured, the leaf has $t-1$ available colours. The chromatic polynomial after attaching a leaf therefore gives

Take the infinite familyEach complete graph is connected and has graph diameter one. If $A_n$ is its adjacency matrix, thenand direct multiplication gives the adjacency-matrix quadratic relation for a complete graphConsequentlyso $I,A_n,A_n^2$, which are precisely the powers through $d(G_n)+1=2$, are linearly dependent for every $n\ge 2$.

Letbe the terminal set, and let $C$ be the vertex set of the given complete graph $K_{2k}$. Any vertex set $S$ meeting every $T$-$C$ path has size at least $2k$: if $|S|<2k$, choose $t\in T\setminus S$ and $c\in C\setminus S$. Since $G$ is $2k$-connected, $G-S$ is connected, so it contains a $t$-$c$ path avoiding $S$, a contradiction.

The Set version of Menger theorem therefore gives $2k$ pairwise vertex-disjoint $T$-$C$ paths. Truncate them at their first and last vertices in $T\cup C$. Since both sets have $2k$ vertices, every terminal is the endpoint of one path and the other endpoints are distinct vertices of $C$. Denote the path from a terminal $z$ to its clique endpoint by $R_z$, and call that endpoint $c_z$.

For each $i$, the clique contains the edge $c_{x_i}{c}_{y_i}$. Concatenatinggives an $x_i$-$y_i$ path in a graph. The linkage paths are mutually vertex-disjoint, their clique endpoints are all distinct, and the joining clique edges pair those endpoints without introducing a new vertex. The resulting paths $P_1,\dots ,P_k$ are therefore mutually vertex-disjoint. In particular, under the stated clique hypothesis, the $2k$-connected graph is $k$-linked for these terminals.

True. Label the vertices $1,\dots ,n$. The cycle $1,2,\dots ,n,1$ uses existing edges of the complete graph and visits every vertex once before returning. It is a Hamiltonian cycle for every $n\ge 3$.

False. A connected graph has an Eulerian cycle exactly when every vertex has even degree. In $K_n$ every degree is $n-1$, so it has an Eulerian cycle precisely when $n$ is odd. The complete graph $K_4$ is a counterexample to the statement for all $n\ge 3$.

Take a complete graph on vertices $a,b,c,d$ and add a fifth vertex $v$ joined only to $a$ and $b$. The minimum degree is two, which is less than $5/2$. The only nonadjacent pairs are $(v,c)$ and $(v,d)$, and each has degree sum $2+3=5$. Thus Ore's condition holds even though the minimum-degree condition fails. For example,is a Hamiltonian cycle in this graph.

Suppose a graph satisfying Ore's theorem were not Hamiltonian. Extend it, on the same vertices, to an edge-maximal non-Hamiltonian graph $H$. Adding edges preserves the degree-sum hypothesis. The complete graph is Hamiltonian, so $H$ has a missing edge $uv$. By maximality, $H+uv$ has a Hamiltonian cycle, which must use the new edge. Removing it gives a Hamiltonian path in $H$, labelled $u=v_1,v_2,\dots ,v_n=v$.

If some $i$ has both edges $u{v}_{i+1}$ and $v{v}_i$, the path can be closed into the cyclecontradicting the choice of $H$. Thus the index sets $\{i:u{v}_{i+1}\in E(H)\}$ and $\{i:v{v}_i\in E(H)\}$ are disjoint subsets of $\{1,\dots ,n-1\}$. Their sizes are ${\mathrm{deg}}_{H}u$ and ${\mathrm{deg}}_{H}v$. Consequently ${\mathrm{deg}}_{H}u+{\mathrm{deg}}_{H}v\le n-1$, contradicting the degree-sum condition for the nonadjacent pair $u,v$. Hence the original graph is Hamiltonian.

In the complete graph every pair of vertices is adjacent, so all $n$ colours assigned to vertices must be distinct. Choose colours successively, leaving one fewer choice at each step. ThusFor nonnegative integer $k<n$ the product is zero, as required.

Put $A=R(k-1,\ell )$, $B=R(k,\ell -1)$ and consider any coloring of $K_{A+B}$. Choose a vertex $v$. Among its $A+B-1$ neighbors, either at least $A$ are joined to it by red edges, or at least $B$ by blue edges.

In the red case, the induced complete graph on those neighbors contains either a red $K_{k-1}$, which joins with $v$ to make a red $K_k$, or a blue $K_{\ell }$. The blue case similarly gives a red $K_k$ or a blue $K_{\ell -1}$ which extends with $v$ to a blue $K_{\ell }$. Hence every coloring has the required configuration, andThis is the Ramsey number recursion.

Here is an explicit simplicial complex on six vertices. Take every subset of one of the following ten triangular facets:For example, $135$ denotes $\{1,3,5\}$, with all its edges and vertices included. Its one-skeleton has all fifteen edges of the complete graph. Every edge belongs to exactly two triangles. The links of a simplex at the six vertices are the following cycles, with the first vertex understood to repeat at the end:Thus every vertex has a disk neighbourhood, as do edge and face interior points. The realization is a compact connected surface without boundary. Its Euler characteristic isThe classification theorem for surfaces identifies the unique closed connected surface with this Euler characteristic as the real projective plane. Consequently this complex triangulates ${\mathbb{RP}}^2$. The explicit facet and link checks make this a genuine simplicial complex, not a polygon whose boundary identifications have been mistaken for simplicial faces.

A planar graph admits at least one graph drawing in which edges meet only at common endpoints. This is a property of the abstract graph, not a requirement on every graph drawing. A plane graph specifies one such drawing.^[ref]

For example, the complete graph $K_4$ joins every pair of four vertices, giving six edges. Put its vertices at the corners of a square and its diagonals cross. Instead put $A,B,C$ at the corners of a triangle and $D$ inside it: the same six edges $AB,AC,BC,AD,BD,CD$ now meet only at their endpoints. The first graph drawing obscures planarity; the second proves it. In particular, its crossing number is zero.

The distinction matters whenever connections must fit on one surface without intersecting. A failed graph drawing may only need rearrangement, whereas nonplanarity by edge counts proves that every rearrangement fails.

A finite simple graph that is a connected graph and a planar graph, with $n\ge 3$ vertices and $m$ edges, satisfies $m\le 3n-6$. Choose a plane graph: each facial boundary walk has length at least three, so $3f\le 2m$. Substitute $f=2-n+m$ from the Euler formula for a connected planar graph.^[ref]

The complete graph $K_4$ attains equality: $6=3\cdot 4-6$. The bound also holds for a disconnected finite simple graph that is a planar graph with $n\ge 3$: place its connected components of a graph in disjoint regions and join them with new bridges in a graph, then apply the connected bound.

The Rado graph is the unique countably infinite graph with the two-uniform hypergraph extension property. Equivalently, for any disjoint finite vertex sets $U,W$, some new vertex is adjacent to every member of $U$ and no member of $W$. The back-and-forth method proves uniqueness. Independent edge sampling on the natural numbers with any fixed $p\in (0,1)$ produces this graph almost surely. It contains both edges and nonedges and therefore is not a complete graph. Its first-order axioms constitute the theory of the random graph.

For positive integers $s,t$, the Ramsey number $R(s,t)$ is the least integer $n$ such that every red-blue edge coloring of the complete graph $K_n$ contains either a red clique on $s$ vertices or a blue clique on $t$ vertices. The complete graph $K_n$ has all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ 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, $R(3,3)$ asks how many vertices force a monochromatic triangle in a graph. Swapping colors gives $R(s,t)=R(t,s)$. Also $R(2,t)=t$: either a red edge exists, or all edges are blue. On $t-1$ vertices, an all-blue coloring avoids both a red edge and a blue $t$-clique. Under the convention that a one-vertex clique qualifies in either color, $R(1,t)=R(s,1)=1$.

For $s,t\ge 2$, splitting the neighbors of one vertex by the colors of their incident edges givesIndeed, in a complete graph of the order on the right, at least $R(s-1,t)$ neighbors are joined to that vertex by red edges, or at least $R(s,t-1)$ are joined by blue edges. In the red case, the defining property of the smaller Ramsey number supplies either a blue $t$-clique among the neighbors or a red $(s-1)$-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 $R(s,t)$ vertices has an $s$-clique or a $t$-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.

Every red-blue edge coloring of the complete graph $K_6$ contains a monochromatic triangle in a graph, and some coloring of $K_5$ contains none. Together the five-cycle Ramsey coloring and six-vertex monochromatic triangle argument giveThe threshold is exact: one carefully chosen coloring establishes the lower bound, while the upper bound must handle every coloring.

A familiar interpretation uses six people and colors each pair red if they know one another and blue if they do not. Assuming the relation is symmetric and every pair falls into exactly one case, there are either three mutual acquaintances or three mutual strangers. The conclusion concerns all three pairs within the group, not merely two relationships through a common person. There is no prediction about which color wins or which three people form the group.

The small size makes exhaustive verification practical. The complete graph $K_5$ has $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ edges, giving $2^{10}=1024$ red-blue colorings of labeled vertices; exactly 12 have no monochromatic triangle in a graph. They are the choices of a red cycle graph of length five, whose blue complement graph is another five-cycle. The complete graph $K_6$ has $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ edges, giving $2^{15}=32768$ colorings. Checking all $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ triples in every coloring finds none without a monochromatic triangle in a graph; in fact the minimum number is two. These counts can be reproduced by assigning one bit to each unordered pair and testing whether the three bits of each triple agree. The monochromatic-triangle counting formula gives a separate explanation of the stronger minimum-two conclusion.

Ramsey theory studies configurations that every finite coloring of a sufficiently large structure must contain. Its striking message is that some order is unavoidable even when no organized construction was used. A basic example is the Ramsey number for triangles: color every edge of a complete graph on six vertices red or blue, in any way, and some triangle in a graph has all three edges the same color. Five vertices do not suffice.

The objects receiving colors matter. In the Ramsey number for triangles, colors belong to edges, which represent all unordered pairs of distinct vertices; the vertices themselves have no colors. In the finite Ramsey theorem, colors can instead belong to all $r$-element subsets of a finite set. A monochromatic set or homogeneous set for a colouring expresses agreement among the appropriate colored objects.

Why is this useful? Ramsey theory provides existence guarantees in combinatorics that survive every possible assignment of a fixed finite number of colors. The Ramsey theorem turns this into a structural dichotomy: every sufficiently large graph contains a large clique or a large independent set. In arithmetic, the Van der Waerden theorem guarantees monochromatic arithmetic progressions. The beauty is the universal quantifier: an adversary can choose every color and still cannot prevent the promised configuration.

These guarantees concern precisely specified configurations under stated hypotheses. They do not justify selecting arbitrary patterns in empirical data after seeing the data, or attributing statistical significance to a selected pattern. A mathematical guarantee of some monochromatic configuration alone says nothing about the empirical meaning of that configuration.

The subject's name comes from F. P. Ramsey's ^[ref]. The ^[ref] records receipt on 28 November 1928 and presentation on 13 December 1928. Ramsey introduced the Ramsey theorem for r-sets and finite Ramsey theorem as tools for a problem in mathematical logic, while recognizing their independent interest in combinatorics. He also distinguished proving that a finite threshold exists from finding its smallest value, the quantitative question captured by a Ramsey number.

In a dense graph with many common neighbours for every pair of vertices, choose disjoint random small sets. A set is good if few vertices have no neighbour in it. The Markov inequality controls the number of bad sets, and random sampling makes almost every pair of good sets adjacent. Add unused common neighbours to connect each set and to repair the remaining missing adjacencies. If the number of used vertices stays below every common-neighbour count, this constructs disjoint branch sets of a graph minor representing a large complete graph.

The ratio convention for cutoff for Markov chains requires $t_{\mathrm{mix}}^{(n)}(\epsilon )/t_{\mathrm{mix}}^{(n)}(1-\epsilon )\to 1$ for every fixed $0<\epsilon <1/2$, with positive denominators eventually. Equivalently, any two fixed levels have asymptotically equal mixing times. This convention permits a bounded-time jump; definitions which additionally require diverging mixing times exclude such a jump. For nonlazy simple random walk on the complete graph $K_n$, every fixed-level mixing time is eventually one.

Represent a finite simple graph by a domain $D$ of vertices and a symmetric, irreflexive binary relation $E$ for graph adjacency. Introduce three unary second-order relation variables $C_1,C_2,C_3$, one for each fixed named colour. Define the following abbreviations for first-order formulas in this expanded first-order signature:Then the existential second-order logic sentenceasserts that every vertex receives exactly one of the three colours and adjacent vertices receive different colours. The first clause gives coverage and pairwise disjointness of the three subsets; the second makes each subset an independent set. Empty colour classes are allowed, so ${\Phi }_3$ expresses existence of a proper vertex coloring using at most three colours.

For the complete graph $K_3$ on the fixed vertices $a,b,c$, one witness is $C_1=\{a\}$, $C_2=\{b\}$, $C_3=\{c\}$. Each vertex satisfies exactly one predicate, and each of the three edges joins different predicates. Every valid witness assigns different colours to all three vertices; there are $3!=6$ witness triples with these fixed vertex labels and fixed named colours. We are counting assignments, without identifying them under colour permutations or graph isomorphisms. For the complete graph $K_4$, the pigeonhole principle forces two of its four vertices to share a colour, and those vertices are adjacent. Thus it has no witness triple. This calculation illustrates a complexity certificate without requiring the reader to reconstruct a machine computation.

Reproduce the diagram by running python ../second-order-coloring-witness.py from the repository's _media directory. The script checks all witness triples for these two complete graphs before drawing them.

Offer $k$ independent uniform edges of the complete graph per row and permit any one to be selected from each row. If a chosen graph has no graph component of order at least $2n/3$, the balanced component cut provides an empty cut whose sides both have at least $n/3$ vertices. Each candidate edge crosses that cut with probability at least $4/9$, so a row can avoid crossing with probability at most $1-(4/9{)}^k$. The union bound over at most $2^n$ cuts gives failure probability at most $2^n[1-(4/9{)}^k{]}^{cn}$. Any fixed integer $c$ with $c[-\log (1-(4/9{)}^k)]>\log 2$ suffices. The guarantee is simultaneous even for choices made after seeing every offered edge.