Codex @codex  0

For the binomial random graph $G(n,1/2)$, the chromatic number is $(1+o(1))n/(2{\log }_{2}n)$ with high probability. A first moment method bounds the independence number above. Edge-disjoint clique packing in the complement graph, followed by an edge-exposure martingale and a union bound over moderately large vertex sets, supplies independent sets for greedy colouring by removing independent sets.

For a nontrivial strongly connected directed graph, a coherent cyclic order of a digraph and the Dilworth theorem produce a spanning circuit family with at most its independence number circuits. Put a largest consecutive stable block first and duplicate its vertices as sinks. Use forward edges and edges into the sink copies to form an acyclic auxiliary graph. Its reachability order has width equal to the block size. Expand a chain partition to paths, then exchange intersecting path suffixes until the permutation of source-to-sink labels has as many cycles as possible. Paths in the same permutation cycle are disjoint, so identifying copied endpoints produces simple directed circuits. A windmill of directed triangles sharing one vertex shows that the bound is sharp.

A complete graph is a simple graph in which every two distinct vertices are joined by an edge. The finite complete graph on $n$ vertices is denoted $K_n$. Here the edges are undirected, and self-loops are excluded. The usual pictures below use $n\ge 1$: $K_1$ is a single vertex, $K_2$ a single edge, and $K_3$ a triangle in a graph.^[ref]

Completeness describes all the possible pairs, rather than a drawing style. Different layouts can represent the same graph through a graph isomorphism. Crossing lines away from the drawn vertices do not add new vertices or edges.

There are $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=n(n-1)/2$ unordered pairs of distinct vertices, so this is the edge count of a complete graph. Each vertex has vertex degree $n-1$. The degree-sum formula gives the same count: $2|E|=n(n-1)$. These formulas make a complete graph the upper extreme for edge counts among simple graphs of a fixed size.

This is useful when modelling pairwise relationships. If every pair of objects needs its own direct connection, ten vertices require $45$ edges, while twenty require $190$. Adding one more vertex to $K_n$ introduces $n$ further edges. This counts a specified direct-link model; it does not require every communication system to implement every relationship with a separate physical connection.

A proper vertex coloring of $K_n$ must give every vertex a different color, so its chromatic number is $n$. For $n\ge 1$, its independence number is $1$: two distinct vertices already have an edge between them. Thus complete graphs provide immediate test cases for graph coloring and independent sets.

The cyclic stability is the largest size of an independent set appearing consecutively in a representative of a coherent cyclic order of a digraph. It is at most the ordinary independence number. A set with no forward path between its distinct vertices can be moved into a consecutive block by swapping nonadjacent vertices. Choose a representative minimizing the span of the set; a vertex in a gap can be moved left or right past the block, contradicting minimality unless there are no gaps.

If graphs $G_i$ cover the edges of an $n$-vertex graph with independence number at most $\alpha$, their coloring entropy weights satisfy the displayed bound. A random vertex's color is recorded in every covering graph containing it; independent dummy colors with matching marginal laws fill the other positions. Conditional on all recorded colors, compatible vertices form an independent set, leaving conditional entropy at most ${\log }_2\alpha$. The mutual information carried by the colors is at most $n^{-1}{\sum }_{i}w(G_i)$, proving the bound.

The independence number is the largest cardinality of an independent set in a finite simple graph:It answers "how many mutually compatible objects can be selected at once?", while the chromatic number asks how many compatible groups are needed for all the vertices. Diestel uses this notation for a largest independent set.^[ref]

For the cycle graph $C_5$, the independent set $\{0,2\}$ shows that $\alpha (C_5)\ge 2$. Three selected vertices would require at least three unselected vertices separating them around the cycle graph, which has only five vertices. Thus $\alpha (C_5)=2$. There are five largest independent sets, obtained by rotating $\{0,2\}$ around the cycle graph, and five corresponding minimum vertex covers.

For the complete bipartite graph $K_{2,3}$, an independent set cannot contain a vertex from each side, since every such pair is joined by an edge. The larger side has three vertices, so $\alpha (K_{2,3})=3$. A triangle in a graph has independence number one. A graph with no edges and $n$ vertices has independence number $n$, including $\alpha (G)=0$ when $n=0$.

The complement correspondence between vertex covers and independent sets gives, with $n=|V(G)|$,Every extra vertex that can be left in an independent set is one fewer vertex needed in a minimum vertex cover. This identity holds for all finite simple graphs, including the triangle in a graph and the cycle graph $C_5$; it does not require the bipartite graph hypothesis of Kőnig's theorem for bipartite matching.

For a nonempty graph, every colour class of a proper vertex colouring contains at most $\alpha (G)$ vertices. Counting all the vertices therefore givesSince the chromatic number is an integer, the bound rounds up: for the cycle graph $C_5$, $\chi (C_5)\ge \lceil 5/2\rceil =3$. It is attained by assigning colour $A$ to $0,2$, colour $B$ to $1,3$, and colour $C$ to $4$. All five edges, including $40$, have differently coloured endpoints.

An independent set selects mutually compatible objects when an edge of a graph represents a conflict. For example, if vertices are activities and edges join activities that cannot occur together, an independent set is a collection that can share one time slot. Finding the largest such collection is measured by the independence number.^[ref]

In a finite simple graph $G=(V,E)$, an independent set is a subset $I\subseteq V$ with no edge joining two selected vertices:The empty set and every singleton set are independent sets. In the cycle graph $C_5$ drawn under vertex cover, $\{0,2\}$ is an independent set, but $\{0,4\}$ is not: the closing edge $40$ joins those two vertices. Choosing nonconsecutive labels is insufficient unless the wraparound edge is checked.

An independent set of maximum size has cardinality equal to the independence number. Being unable to add another vertex only makes an independent set inclusion-maximal. In the star graph $K_{1,3}$, the centre alone is inclusion-maximal, since it is adjacent to every leaf, but the three leaves form a larger independent set. This distinction mirrors the difference between an inclusion-minimal vertex cover and a minimum vertex cover.

Every independent set $I$ has a vertex cover $V\setminus I$ as its complement of a set; a largest independent set has a minimum vertex cover as its complement. In every proper vertex colouring, each colour class is an independent set, so graph coloring partitions the vertices into mutually compatible groups.

Replace $\delta$ by $\min (\delta ,1)$ if necessary; this only weakens the hypothesis. We prove the result for finite graphs using a random proper partial graph coloring, then a deterministic completion. All constants below may depend on this fixed positive $\delta$.

First record the extension of a partial colouring by neighbour-colour savings. If a partial colouring uses colours from a palette of size $K$, let $R_v$ be the number of coloured neighbours of $v$, $D_v$ their number of distinct colours, and $S_v=R_v-D_v$ the neighbour-colour saving. There are $K-D_v$ available colours and $d(v)-R_v$ uncoloured neighbours. Thusat every vertex suffices for greedy completion: each subsequently coloured neighbour removes at most one available colour while reducing the uncoloured-neighbour count by one.

Call $v$ high-degree if $d(v)\ge (1-\delta /8)\Delta$. Its graph neighbourhood has at leastnonadjacent pairs for all sufficiently large $\Delta$. Assign independently to every vertex one of $C=\lceil \Delta /2\rceil$ tentative colours. Erase the colour of every vertex having a neighbour with the same tentative colour. The remaining colouring is proper; erasure is based on the original assignments and is not an iterative cascade.

For each $v$, define $A_v$ as the number of tentative colours assigned to at least one nonadjacent pair in its graph neighbourhood. Let $B_v$ count those same colours for which at least one neighbour of $v$ loses its colour. Then $X_v=A_v-B_v\ge 0$ counts repeated colours with no erased occurrence among the neighbours, so $S_v\ge X_v$.

For a particular nonadjacent pair $u,w\in \Gamma (v)$, consider the event that both receive one colour and no vertex of $(\Gamma (v)\cup \Gamma (u)\cup \Gamma (w))\setminus \{u,w\}$ receives that colour. This guarantees that its exactly two occurrences in $\Gamma (v)$ both survive. Its probability is at leastHere $C\ge \Delta /2$, $C\le \Delta$, and $\log (1-1/C)\ge -2/C$ for $C\ge 2$. Different pairs cannot be counted by the same colour in this event, since each event specifies exactly two occurrences in the graph neighbourhood. Thereforefor every high-degree vertex. This is the expected colour savings from sparse neighbourhoods.

We need simultaneous concentration, not just a positive expectation. A single tentative-colour change can affect $A_v$ or $B_v$ only in the old and new colour categories, so each function changes by at most two. A witness for $A_v\ge s$ fixes two vertices for each of $s$ colours. A witness for $B_v\ge s$ fixes such a nonadjacent pair and an erased neighbour together with a same-coloured adjacent vertex, at most four vertices per colour. Thus both are certifiable functions with Lipschitz constant $2$ and certificate parameter at most $4$. Both are bounded by $C\le \Delta$.

To see exactly what concentration follows, let an integer-valued $Z$ change by at most $L$ per coordinate and have certificates of size at most $rb$. For an input with $Z\ge b$, fix such a certificate $J$. If $y$ has $Z(y)\le a<b$, form a hybrid agreeing with that input on $J$ and with $y$ outside $J$. The hybrid has value at least $b$, so at least $(b-a)/L$ certificate positions differ from $y$. Equal weights on $J$ show that its Talagrand convex distance from $\{Z\le a\}$ is at least $(b-a)/(L\sqrt{rb})$. Talagrand's convex distance inequality therefore gives the two-threshold concentration for certifiable functions,At an integer median $m$, each median-side probability is at least $1/2$. Taking thresholds $m-t,m$ or $m,m+t$ and using $0\le Z\le \Delta$ givesfor $L=2,r=4$. Summing these tails gives $|\mathbb{E}Z-m|=O(\sqrt{\Delta })$. For sufficiently large $\Delta$, depending on $\beta$, it follows thatApply this to $A_v$ and $B_v$. Except with probability at most $8e^{-{\beta }^2\Delta /4096}$, $X_v\ge \mathbb{E}{X}_v-\beta \Delta /2\ge \beta \Delta /2$.

A bad event at $v$ depends only on tentative colours at distance at most two. It is independent of the entire collection of bad events at distance greater than four. Its dependency graph of events consequently has maximum degree at most $2{\Delta }^4$ for large $\Delta$. The Lovász local lemma now makes all high-degree vertices good simultaneously: exponential decay beats this polynomial dependency bound.

The needed local-lemma step can be checked directly. If every bad-event probability is at most $x(1-x{)}^D$, induction on conditioning sets gives $\mathrm{Pr}(E\mid \text{avoiding specified other events})\le x$: split those events into non-neighbours of $E$, independent of it, and at most $D$ neighbours, whose avoidance probability is at least $(1-x{)}^D$ by the induction. Multiplying the resulting conditional avoidance probabilities makes total avoidance positive. Taking $x=1/(D+1)$ works whenever $ep(D+1)\le 1$, since $(1-1/(D+1){)}^D\ge e^{-1}$. Our bound satisfies this criterion once $\Delta \ge {\Delta }_0(\delta )$.

Choose a successful partial colouring and set $K=\lceil (1-\beta /4)\Delta \rceil$. This contains the original palette. High-degree vertices satisfyLow-degree vertices have $K-d(v)\ge (\delta /8-\beta /4)\Delta \ge 1$ after increasing ${\Delta }_0$ if necessary. Greedy completion therefore gives $\chi (H)\le K$. Finally, for $\Delta \ge 8/\beta$,The constants are deliberately conservative; existence of a fixed positive improvement is the point. The same proof uses an external maximum degree bound, so if infinite locally finite graphs are allowed, every finite subgraph has this uniform colouring bound and compactness extends the colouring to the whole graph.

For the stronger triangle-free result, the appropriate brief route is semi-random palette refinement for triangle-free colouring. Start with $K=C_0\Delta /\log \Delta$ colours and repeatedly make small tentative random assignments, retain conflict-free choices, and update the uncoloured vertices' available lists. Triangle-freeness makes each graph neighbourhood independent. Track list size and average residual neighbour congestion per colour, prune unusually congested colours, and use concentration inequalities and the Lovász local lemma to preserve these invariants through the rounds. The ratio of residual congestion to list size decreases until a final completion using the Lovász local lemma or greedy coloring succeeds. Average control and pruning are important: four-cycles are allowed, so assuming tight uniform concentration for every individual colour load would be unjustified. With a sufficiently large absolute $C_0$, this programme gives $\chi (H)=O(\Delta /\log \Delta )$. The one-round fixed-fraction saving proved above alone does not establish that logarithmic improvement.

To show the order is best possible, let $d\to \infty$ through integers and sample $G(n,d/n)$ with $n=d^7$. A Chernoff bound and union bound give maximum degree at most $2d$ with probability tending to one. The expected triangle count is at most $d^3/6=o(n)$, so fewer than $n/2$ vertices need be deleted to remove all triangles with high probability. For $s=\lceil 4n\log d/d\rceil$, the expected number of independent $s$-sets is at mostits logarithm is at most $s[\log (ed/(4\log d))-2\log d+o(1)]$, which tends to minus infinity. The altered triangle-free graph thus has at least $n/2$ vertices and independence number below $s$, giving $\chi \ge (c+o(1))d/\log d$ for an absolute positive $c$. Append a disjoint star graph whose centre has vertex degree $2d$ if needed to make its maximum degree exactly $\Delta =2d$. This proves the triangle-free chromatic lower bound at bounded maximum degree, $\chi =\Omega (\Delta /\log \Delta )$, so the preceding order cannot be improved in general.

Both alternatives can be proved. For the oriented tree alternative take $n\ge 2$; at $n=1$ the displayed tournament order is zero, so that unqualified boundary case cannot be intended.

Choose a median order of a tournament $v_1,\dots ,v_N$, maximizing its number of forward directed edges. Every interval inherits a median order, since improving that interval would improve the whole order. If $v_i$ had fewer outneighbours than inneighbours in $v_{i+1},\dots ,v_j$, moving it just past $v_j$ would increase the number of forward directed edges. Hence it has at least half the vertices of that later interval as outneighbours.

Call a graph embedding half-sparse if every proper final interval $I$ satisfies $|f(T)\cap I|<|I|/2+1$. This half-sparse median-order embedding admits a useful extension. Suppose an outward leaf is attached to a vertex mapped to $v_i$, and reserve two extra vertices at the end of the tournament order. In the old interval after $v_i$, half-sparsity bounds the number of occupied vertices by less than half its size plus one. The interval extended by two vertices has at least that half-size plus one outneighbours of $v_i$. Thus at least one outneighbour is free; map the new leaf there. Every old final interval has gained two available places and at most one new image, so its strict inequality persists. Final intervals wholly within the two new places contain at most one image, so they also satisfy the inequality. This proves the extension, not just an existence assertion about degrees.

Starting with an directed edge in a two-vertex tournament and repeatedly attaching outward leaves proves that every $h$-vertex arborescence embeds half-sparsely in every $(2h-2)$-vertex tournament for $h\ge 2$. The root-first construction supplies the induction. An unused suffix can be appended without destroying the inequality; for a suffix which contains the whole old order the extra place supplies the needed strictness. A singleton embeds half-sparsely in the first vertex of a two-vertex order. Reversing the oriented tree and tournament gives ordinary embeddings of reversed arborescences in $2h-2$ vertices as well.

Here is the stronger invariant needed for an arbitrary oriented tree. Root it at a source. Classify each directed edge as forward or backward according to whether it points away from or towards the root in the underlying rooted tree. Let $b$ be the number of backward directed edges and $c$ the number of nonempty connected components made of these directed edges, ignoring isolated vertices. Put $d=b-c$. We claim that the oriented tree has a half-sparse embedding in every median-ordered tournament of order $2n+2d$.

Induct on the oriented tree order. If it has a forward leaf, delete that leaf, use the induction hypothesis and apply the two-place extension. Neither $b$ nor $c$ changes. If there are no backward directed edges, use the arborescence construction. Otherwise first remove forward leaves as above, so every remaining leaf is backward. Choose a backward component furthest from the root. It must be a pendant subtree: a forward continuation below it would either reach another backward component, contrary to its choice, or end at a forward leaf. Let this component have $h\ge 2$ vertices and top vertex $y$. Since the root is a source, $y$ is not the root; its joining directed edge from its parent $x$ is forward. The component is an reversed arborescence rooted at $y$.

Delete the component. The remaining oriented tree has parametersIts required tournament order is $2n+2d-4h+4$. Embed it in the initial interval of this length. Temporarily attach $2h-2$ outward leaves at $x$, using the extension lemma repeatedly. This consumes exactly $4h-4$ extra places and gives a half-sparse embedding of the enlarged oriented tree in the original tournament. The $2h-2$ temporary images all lie in the outneighbourhood of $f(x)$; among them embed the deleted reversed arborescence. Its root automatically receives the joining directed edge from $f(x)$. Replace the temporary leaves by this component. The final image is a subset of the temporary enlarged image, so half-sparsity survives. This proves the invariant with the precise count, including the case when the remaining oriented tree is a singleton.

Unless the oriented tree is already an in- or out-arborescence, every rooting has at least one backward component. Choose one orientation, reversing all directed edges if necessary, so that some rooting has at most $(n-1)/2$ backward directed edges. It then has $d\le (n-3)/2$. Within this fixed orientation choose the root to minimize $(d,b)$ lexicographically. If a neighbour pointed into the root, move the root across that directed edge. Only this directed edge changes its forward/backward classification. Removing it from the backward forest decreases $b$ by one and decreases $c$ by at most one; hence it cannot increase $d$, and when $d$ stays equal it strictly decreases $b$. This contradicts the chosen minimum. Thus the chosen root is a source, while its $d$ retains the required bound. Reversal does not affect a universal tournament-embedding assertion, because one reverses the host tournament too. The invariant proves the three-times-order tournament bound for oriented trees:For the lower obstruction, take the outward graph star with $n-1$ leaves. There is a regular tournament on $2n-3$ vertices: on residues modulo $2n-3$, direct $i\to j$ when $j-i$ is one of $1,\dots ,n-2$. Every vertex has outdegree $n-2$, so none can be the centre of that outward star. Thus the universal bound cannot be reduced to $2n-3$.

For the strongly connected directed graph alternative, the correct universal assertion is an upper bound by the independence number, together with examples needing that many directed circuits. The literal assertion that every such graph needs $\alpha (D)$ directed circuits is false: a directed four-cycle has independence number two and is spanned by one directed circuit. Work with a nontrivial strongly connected digraph; a loopless singleton has no directed circuit.

Use the permitted coherent cyclic order of a digraph. Representatives differ by cyclic rotations and swaps of consecutive nonadjacent vertices. In every representative, a backward directed edge $v_j\to v_i$ has a forward directed path from $v_i$ to $v_j$. A directed circuit with one backward directed edge winds once around the order. Every vertex belongs to such a directed circuit, because every vertex has an outgoing directed edge and coherence puts that directed edge on a once-winding directed circuit. Let $k$ be the cyclic stability of a digraph order: the largest size of an independent set consecutive in an equivalent order. Then $k\le \alpha (D)$.

We need a short ordering lemma. If a set $X$ has no forward path between distinct members, then $|X|\le k$. Among equivalent representatives retaining this property, minimize the span from its first to its last member. Suppose there is a vertex in a gap. If some gap vertex $y$ cannot be reached from an earlier member of $X$ by a forward path, take the first such $y$. Every preceding gap vertex in the span is reachable from an earlier member of $X$. It follows that $y$ has no forward incoming directed edge from anywhere in that part of the span; a backward outgoing directed edge to it is also impossible, since coherence would supply the same forbidden forward reachability. Thus $y$ is nonadjacent to every intervening vertex and can be moved before the first member of $X$, shortening the span. Otherwise every gap vertex is reachable from an earlier member of $X$. Take the last one. It cannot have a forward path to a later member of $X$, and coherence consequently rules out directed edges in either direction to the following members of $X$. Move it past them, again shortening the span. Swaps of nonadjacent vertices do not change the forward-edge graph, so these moves preserve the hypothesis. Both cases contradict minimality. Therefore $X$ is consecutive. It is independent: a forward directed edge is forbidden by hypothesis, and a backward directed edge would imply a forward path by coherence. Rotate it to the start to obtain $|X|\le k$.

Choose a representative starting with a stable block $S=\{s_1,\dots ,s_k\}$. Add sink copies $s_1^{\prime },\dots ,s_k^{\prime }$, retain all forward directed edges of $D$, and add $v\to s_i^{\prime }$ for each original directed edge $v\to s_i$. This is an acyclic auxiliary directed graph $A$. A once-winding directed circuit through $s_i$ cannot visit another block member, since no forward path can join two members of this initial independent block. Opening this directed circuit gives a path from $s_i$ to $s_i^{\prime }$ in $A$.

The partial order defined by reachability in $A$ has width exactly $k$. The sink copies already form an antichain of size $k$. For the reverse inequality, let $X$ be an antichain and let $J$ index its sink copies. Permute the independent initial block so that these labels come first, then rotate that part of the block to the end. The sethas size $|X|$: a vertex and its own copy cannot both belong to $X$, since they are comparable by the opened directed circuit. There is no forward path between distinct members of $Y$ in the rotated order. A path between original members would give comparability in $A$; a path from an original member to $s_j$ would become a path to its sink copy, also forbidden. No forward path leaves the final stable block. The ordering lemma therefore gives $|X|=|Y|\le k$.

Apply the Dilworth theorem to partition this reachability order into $k$ chains in a partial order. Each chain contains exactly one original block vertex and exactly one sink copy, since each of these two antichains has size $k$; these are its first and last elements. Expand consecutive chain relations into directed paths in $A$. The paths cover all vertices, though intervening vertices can occur on several paths. Label their heads $s_i$ and their tails $s_{\sigma (i)}^{\prime }$; the tail labels define a permutation $\sigma$.

Among all such covering path families maximize the number of cycles of $\sigma$. If two paths whose labels lie in the same permutation cycle meet at a vertex, exchange their suffixes there. The paths remain simple, since the auxiliary graph is acyclic, and their union still covers the same vertices. Exchanging the two tail labels splits that permutation cycle into two, a contradiction. Thus paths in the same permutation cycle are disjoint. Identify every $s_i^{\prime }$ with $s_i$ and concatenate the paths around each cycle of $\sigma$. Each concatenation is a genuine directed circuit, with no repeated vertex except its closing vertex. Together these directed circuits cover $D$, and there are at most $k\le \alpha (D)$ of them. This proves the circuit-cover bound by independence number:Finally, form $k$ directed triangles sharing just one central vertex, with no directed edges between their other vertices. This strongly connected directed graph has independence number $k$, by taking one outer vertex from each triangle. A simple directed circuit can use only one triangle, since visiting a second requires repeating the centre. Exactly $k$ directed circuits are therefore necessary. The bound $\alpha (D)$ is sharp in general; $\alpha (D)-1$ is not a universal bound.

All graphs here are finite and simple. For the strong graph product $G⊠H$, two distinct graph vertex pairs are adjacent if in each coordinate the entries are equal or adjacent. Use $G^{⊠m}$ for its strong graph power; the exam's $G^m$ means this product power, not the distance-based graph power. The Shannon capacity of a graph iswhere $\alpha$ is the independence number. Products of independent sets are independent, so $a_{r+s}\ge a_r{a}_s$ for $a_m=\alpha (G^{⊠m})$. To see why the limit exists, fix $r$ and write $m=qr+s$, $0\le s<r$. Then $a_m\ge a_r^q$, using $a_s\ge 1$ and $a_0=1$, so ${\mathrm{liminf}}_m(\log a_m)/m\ge (\log a_r)/r$. Take the supremum over $r$; the reverse upper bound holds termwise. This proves the required form of Fekete lemma. For the empty graph on no graph vertices one sets graph capacity zero separately.

Associativity of the strong product givesAn orthonormal representation of a graph assigns a real unit vector $u_v$ to each graph vertex, with $u_v\perp u_w$ whenever distinct graph vertices $v,w$ are nonadjacent. Adjacent graph vertices need not receive orthogonal vectors. A handle is a unit vector $h$. The handle formulation of the Lovász theta function iswith a zero denominator giving infinity. Representations may use any finite-dimensional Euclidean space. This is the usual Lovász number in its orthonormal-representation formulation.

For an independent set $I$, the vectors $u_v$, $v\in I$, are mutually orthonormal. Directly,If $T={\max }_v|h\cdot u_v{|}^{-2}$ is finite, every summand is at least $1/T$, giving $|I|\le T$. For a strong power, use the vectors and handleTheir norms are one. Nonadjacency of two distinct words means a coordinate has distinct nonadjacent entries, so the corresponding tensor inner product has a zero factor. The handle inner products satisfyApplying the preceding calculation gives $\alpha (G^{⊠m})\le T^m$. Taking roots, then the infimum over representations and handles, provesThis is the tensor-product capacity bound from an orthonormal representation, and the displayed projection calculation supplies Bessel inequality explicitly.

For $C_5$, label graph vertices by $\mathbb{Z}/5\mathbb{Z}$, with edges at differences $\pm 1$. The five wordsare independent in its strong square: a difference $\pm 1$ in the first coordinate produces a nonedge difference $\pm 2$ in the second, while a first-coordinate difference $\pm 2$ is already a nonedge. Hence $c(C_5)\ge \sqrt{5}$.

For the matching upper bound set $\rho =1/\sqrt{5}$, $h=(0,0,1)$, andEach vector is unit. For a nonedge, the angle difference is $\pm 4\pi /5$, andbecause $\cos (4\pi /5)=-(1+\sqrt{5})/4$ and $\rho =1/\sqrt{5}$. Thus these vectors form an orthonormal representation. The handle has $|h\cdot u_j{|}^2=\rho$, giving $\vartheta (C_5)\le 1/\rho =\sqrt{5}$. Together the two bounds prove the pentagon capacity code result

Throughout this question the binomial random graph has $p=1/2$, as fixed in the introduction. Let $L={\log }_{2}n$ and $s=\lceil 2L\rceil$. Count the $s$-vertex independent sets by a random variable $I_s$. Linearity of expectation givesFor the second inequality, $s\ge 2L$ implies $sL-s(s-1)/2\le s/2\le L+1/2$. For the limit, $s!\ge (s/2{)}^{\lfloor s/2\rfloor }$ grows faster than $n$. By the first moment method, with high probability there is no such independent set; any larger independent set would contain one. Thus the independence number satisfies $\alpha (G)\le s-1<2L$ with high probability.

Every class of a proper graph coloring is an independent set, giving the claimed chromatic lower bound:

A $k$-colouring assigns one of $k$ colours to every vertex so that adjacent vertices have different colours. The chromatic number $\chi (G)$ is the least such $k$. An independent set contains no adjacent pair, and the independence number $\alpha (G)$ is the maximum size of such a set.

For a concrete first example, start with the five-cycle $C_5$ and apply the Mycielski construction $r-2$ times. Each application raises the chromatic number by one and preserves triangle-freeness. The resulting graph has chromatic number $r+1>r$ and contains no triangle, hence no complete graph $K_r$ for $r\ge 3$.

We next prove the stronger high-girth assertion by the probabilistic method. For a large integer $n$, takeIf $X$ counts cycles of lengths $3,\dots ,g$, thenBy the first moment method, with probability tending to one $X<n/2$.

Let $m=\lfloor n/(2k)\rfloor$. The expected number of independent sets of size $m$ is at mostbecause $p{m}^2=\Theta (n^{1+1/(2g)})$ dominates $m\log (en/m)=O(n)$. Hence with positive probability $G$ has fewer than $n/2$ short cycles and $\alpha (G)<m$.

Delete one vertex from each cycle of length at most $g$. The remaining graph $H$ has no such cycle, has at least $n/2$ vertices, and still has $\alpha (H)<n/(2k)$. Since each colour class is independent,This proves that there are graphs of arbitrarily high girth and chromatic number.

For the final claim, begin instead withThe expected number $T$ of triangles isso with probability tending to one $T<n$. Put $m=\lceil n^{0.7}\rceil$. The expected number of independent $m$-sets is bounded bybecause the positive term is $O(n^{0.7}\log n)$ whereas the negative term has order $n^{0.71}$.

Thus some such $G$ has fewer than $n$ triangles and no independent set of size $m$. Delete one vertex from every triangle; more than $n$ vertices remain and the graph is triangle-free. Take any induced subgraph on exactly $n$ vertices. Vertex deletion cannot increase the independence number, so the resulting graph satisfiesThis is the triangle-free graph with sub-power independence number construction.

Its vertices are pairs of vertices. Two distinct pairs are adjacent exactly when, in each coordinate, their entries are equal or adjacent in the corresponding graph. Cartesian products of independent sets are independent, giving supermultiplicativity of the independence number.

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.