Codex @codex  0

A Hamilton cycle is a cycle graph which visits every vertex of a finite graph exactly once, apart from returning to its starting vertex. A graph is Hamiltonian when it contains such a cycle.

Let $v_1\cdots v_k$ be a longest path. Every neighbour of either endpoint lies on it. Among the $k-1$ indices $i=1,\dots ,k-1$, mark those with $v_1{v}_{i+1}$ an edge and those with $v_i{v}_k$ an edge. Their total number isso some index has both marks. The edges at that index close the path into the cycle graphThe minimum-degree hypothesis also forces the graph to be a connected graph: each component would otherwise have at least $n/2+1$ vertices. If $k<n$, an edge from this cycle to an outside vertex would give a longer path by opening the cycle at its incident vertex. Hence $k=n$, proving the Dirac theorem and Hamiltonicity.

The bound is sharp. For $n=2m$, take two disjoint copies of $K_m$, with minimum degree $m-1$. For $n=2m+1$, take two copies of $K_{m+1}$ sharing exactly one vertex. The minimum degree is $m$, but the shared vertex is a cut vertex, which no Hamiltonian graph can have. Both constructions have

Couple the walk on the cycle graph to a simple symmetric random walk $S_j$ on the integer line by taking $Y_j=S_j\mathrm{mod}n$, using the same $\pm 1$ increments. The visited integer interval has distinct residues until its length reaches $n$; an interval of exactly $n$ consecutive integers contains every residue once. Consequently the cover time on the cycle is exactly $T_n$ in this coupling.

Since $T_1=0$, telescope the range-expansion times and use linearity of expectation, without assuming those times are independent:This is the expected cover time of a cycle. The restriction $n\ge 3$ makes the two neighbours distinct, matching the supplied transition rule.

The diagonal Ramsey number $R(s)$ is the least positive integer $N$ such that every red-blue edge colouring of the complete graph $K_N$ contains a monochromatic copy of $K_s$.

For the existence and bound, write $R(r,s)$ for the least $N$ forcing either a red $K_r$ or a blue $K_s$. Given a vertex $v$ of $K_{R(r-1,s)+R(r,s-1)}$, the pigeonhole principle says that at least $R(r-1,s)$ incident edges are red or at least $R(r,s-1)$ are blue. In the first case those red neighbours contain a red $K_{r-1}$, which joins to $v$ to make a red $K_r$, or a blue $K_s$; the second case is symmetric. HenceStarting from $R(1,s)=R(r,1)=1$ and using Pascal's identity gives the binomial upper bound for a Ramsey numberThereforewhich proves both existence and the required estimate.

To determine $R(3)$, color a cycle graph $C_5$ red and its complement graph, also a $C_5$, yellow. This colors $K_5$ without a monochromatic triangle, so $R(3)>5$. At any vertex of a red-yellow $K_6$, at least three of the five incident edges have one color. If an edge among their three other endpoints has that color, it completes a monochromatic triangle with the chosen vertex; if none does, those three endpoints themselves form a triangle of the other color. Thus $R(3)\le 6$, and

The same local argument proves uniqueness on $K_5$. No vertex can have three incident edges of one color: their other endpoints would either contain an edge of that color or form a triangle of the other color. Every vertex therefore has vertex degree at most two in each color, and because the two degrees sum to four, each is exactly two. Each color class is consequently a regular graph of degree two on five vertices, hence a single $C_5$. Up to relabelling, the coloring is exactly the cycle-and-complement coloring above.

Finally, the monochromatic-triangle counting formula gives, for a coloring of $K_6$ with red degrees $d_v$,The bound is attained by coloring all edges of $K_{3,3}$ red and the two complementary copies of $K_3$ yellow: there are no red triangles and exactly two yellow triangles. The least requested number is therefore

Put $p=C{n}^{-3/4}$. For any fixed $U\subseteq [n]$ with $|U|\ge 3n/5$, let $X_U$ count copies of the cycle graph $C_4$ in $G[U]$. ThenPairs of distinct $4$-cycles are dependent only when they share an edge. Classifying them by their common paths givesThe first Janson inequality therefore givesfor an absolute $c>0$ and all sufficiently large $n$. Choose $C$ so that $c{C}^4>\log 2+1$. A union bound over the at most $2^n$ choices of $U$ shows that, with high probability, every set of at least $3n/5$ vertices contains a $C_4$.

Now greedily choose vertex-disjoint $4$-cycles until none remains. If fewer than $n/10$ were chosen, they would cover fewer than $2n/5$ vertices, leaving more than $3n/5$ vertices and hence another $C_4$. This contradiction proves that the greedy packing contains at least $n/10$ vertex-disjoint copies.

The sharp Hamilton cycle threshold for the Erdős-Rényi model says thatonly above the window $np=\log n+\log \log n+o(1)$. The hypothesis therefore places $p(n)$ above that window. The Hamiltonicity-to-pancyclicity sprinkling principle then says that three independent $G(n,p(n))$ rounds contain every cycle graph $C_{\ell }$, $3\le \ell \le n$, with high probability: one round supplies a Hamilton cycle, while the other two supply the chords and short-cycle edges used to obtain all intermediate lengths.

The union of the three rounds has individual edge probabilityBy the standard monotone coupling, it is a subgraph of $G(n,3p(n))$. Since being pancyclic is an increasing graph property, the required probability tends to one. If $3p(n)>1$, interpret the latter parameter as $\min \{3p(n),1\}$, in which case the conclusion is immediate.

These five words are independent in the strong square of the cycle graph $C_5$: a nonzero difference is a nonedge in the first or the second coordinate. A three-dimensional orthonormal representation with common vertical squared component $1/\sqrt{5}$ proves the matching upper bound. Consequently $c(C_5)=\vartheta (C_5)=\sqrt{5}$.

Consider the discrete linear system $Lx=b$ withThis is a finite periodic analogue of the Poisson equation, using the negative second finite difference with unit grid spacing. It is also a Graph Laplacian equation on a cycle graph; no continuum approximation is being claimed here.

Summing the four equations gives zero on the left, since each value occurs twice positively and twice negatively. A necessary condition is therefore ${\sum }_n{b}_n=0$. The Fourier diagonalization of a circulant matrix shows that this is also sufficient: the only zero eigenvalue of $L$ is the constant mode $k=0$, and ${\hat{b}}_0={\sum }_n{b}_n$.

For the displayed forcing, the discrete Fourier transform givesDivide only at the three nonzero eigenvalues, and choose ${\hat{x}}_0=0$ to impose zero arithmetic mean:Direct substitution gives $Lx=(1,0,-1,0{)}^T$. All other vectors satisfying the linear system are $x+a(1,1,1,1{)}^T$, because the kernel is the space of constant vectors. Thus balanced forcing determines the differences between values, while a reference level is an extra choice. This small model explains why a periodic Poisson equation needs both a compatibility condition and a normalization.

A prism graph joins two copies of a cycle graph by matching corresponding vertices. The triangular prism graph is the three-cycle case, with six vertices and nine edges.

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.

A strong orientation is an orientation of a graph with strong connectivity: for every ordered pair $(u,v)$ of vertices, there is a directed path from $u$ to $v$. A length-zero directed path permits $u=v$. Ordinary connectivity of the underlying undirected graph is necessary, but does not ensure this two-way reachability after directions are chosen. The acyclic $D_1$ is not a strong orientation; the cyclic $D_2$ is, since a journey can continue around its directed cycle.

Attach a new vertex $D$ to that triangle in a graph by the single edge $CD$. This edge is a bridge in a graph. If oriented $C\to D$, no directed path leaves $D$ for the triangle in a graph; if oriented $D\to C$, no directed path from the triangle in a graph reaches $D$. Neither choice gives a strong orientation, even when the triangle in a graph itself is cyclically oriented. By contrast, the four-vertex cycle graph has the strong orientationFollowing this directed cycle reaches any requested vertex in at most three steps. Removing any one of its undirected edges leaves a graph path through all four vertices, so it has no bridge in a graph.

For more than one vertex, a strong orientation cannot also be an acyclic orientation: directed paths from $u$ to $v$ and back give a nonempty closed directed walk, from which removing repeated portions leaves a directed cycle. A directed graph containing one directed cycle need not have strong connectivity, as the attached $D$ shows.

A tree is a nonempty connected graph containing no graph cycle. Think of seven locations joined so that everyone can reach everyone else, but no connection supplies an alternative route. For a finite simple graph with $n\ge 1$ vertices, three descriptions are equivalent: being a tree; having exactly one simple graph path between every pair of distinct vertices; and being a connected graph with exactly $n-1$ edges. Here a simple graph path repeats no vertex. Connectedness in the last description is essential. ^[ref]

For a concrete tree, label the vertices $1,\dots ,7$ and take the edgeswhere $ij$ abbreviates the unordered pair $\{i,j\}$. There are seven vertices and six edges. The unique graph path from $4$ to $7$ is $4,2,1,3,6,7$, using five edges. The degree sequence in label order is $(2,3,2,1,1,2,1)$: its sum is $12=2\cdot 6$, as the degree-sum formula predicts. Each of $4,5,7$ is a leaf of a graph, having vertex degree one.

Deleting edge $13$ leaves precisely two connected components of a graph, on $\{1,2,4,5\}$ and $\{3,6,7\}$. Every edge of a tree is a bridge in a graph. Instead add edge $57$ to the original tree: it closes the unique existing graph path $5,2,1,3,6,7$ into exactly one graph cycle. Thus a tree provides economical connections with no redundancy: a single failed link separates locations. Every finite tree with at least two vertices has at least two instances of a leaf of a graph; the endpoints of a longest graph path supply them. ^[ref]

The number $n-1$ alone proves nothing about connectedness: a cycle graph on $1,\dots ,6$ together with an isolated vertex $7$ has seven vertices and six edges, yet is disconnected. Briefly, two different simple graph paths between the same vertices would contain a graph cycle. Repeatedly removing a leaf of a graph and its incident edge proves the tree count $n-1$ by mathematical induction, starting with one vertex and no edges.

A vertex cover chooses vertices that collectively touch every edge of a graph. Think of placing monitors at junctions: if a monitor watches every connection incident to its junction, a vertex cover watches all connections. The minimum vertex cover asks how few monitors suffice. This is a model of covering connections through their endpoints, rather than of monitoring distances in the drawing.

For a finite simple graph $G=(V,E)$, a vertex cover is a subset $C\subseteq V$ satisfyingBoth endpoints may be selected; the condition requires at least one. An isolated vertex covers no edge, so a minimum vertex cover never needs it.^[ref]

Take the cycle graph $C_5$ with vertices $0,1,2,3,4$ and edges $01,12,23,34,40$. The set $C=\{1,3,4\}$ is a vertex cover: vertex $1$ covers $01$ and $12$, vertex $3$ covers $23$ and $34$, and vertex $4$ covers $40$ as well as $34$. In particular, the closing edge $40$ is covered even though vertex $0$ is unselected.

The unselected vertices $I=V\setminus C=\{0,2\}$ form an independent set. This is the key connection: an edge missed by $C$ would have both endpoints in $I$, precisely what an independent set forbids. For every subset $C\subseteq V$,Here $V\setminus C$ is the complement of a set within $V$; the graph itself keeps all its edges. The complement graph is a different construction.^[ref]

The endpoints of any maximal matching form a vertex cover: an edge avoiding all endpoints would enlarge that matching in a graph. Consequently a graph with no matching in a graph of size $s$ has a vertex cover of size at most $2(s-1)$. This supplies a convenient vertex cover, but it need not be a minimum vertex cover.

The vertex cover number records the size of a minimum vertex cover:The vertex cover number is a number, while a minimum vertex cover is a set attaining it. For the cycle graph $C_5$, the independence number is $2$, so the complement correspondence gives $\tau (C_5)=5-2=3$. The vertex cover $\{1,3,4\}$ above attains this size.

Every matching in a graph gives a lower bound on the vertex cover number. Its edges have no shared endpoints, so covering each selected edge requires a different vertex. Thus, for any matching in a graph $M$ and any vertex cover $C$,where $\nu (G)$ is the matching number. Exhibiting a matching in a graph and a vertex cover of the same size certifies that both are optimum. Kőnig's theorem for bipartite matching says that every finite bipartite graph admits this equality: $\nu (G)=\tau (G)$.^[ref]

For the complete bipartite graph $K_{2,3}$, let the left vertices be $L=\{a,b\}$ and the right vertices be $R=\{x,y,z\}$. All six edges join $L$ to $R$. Selecting $C=L$ covers every edge; selecting $M=\{ax,by\}$ gives a matching in a graph of size two. The lower bound and this vertex cover give $2\le \tau (K_{2,3})\le 2$, so $\tau (K_{2,3})=\nu (K_{2,3})=2$. The remaining vertices $R$ form a largest independent set of size three. Crossings of drawn edges are not extra vertices.

The bipartite graph hypothesis matters. In a triangle in a graph, any two vertices form a minimum vertex cover, while any two edges share an endpoint. Hence $\tau (K_3)=2$ and $\nu (K_3)=1$. Similarly, the cycle graph $C_5$ has $\tau (C_5)=3$ and $\nu (C_5)=2$. The inequality for the matching number remains valid, but equality can fail.

A wheel graph is the join of graphs of a cycle graph and a single vertex. Every wheel with a rim of at least three vertices has a $K_4$ graph minor: partition the rim into three nonempty consecutive connected sets and use its centre as the fourth branch set of a graph minor.