[proofplan] We use the probabilistic deletion method. Sample $G \sim G(n, p)$ with $p = n^{-1+1/g}$ and simultaneously control two quantities: the number $X$ of short cycles (length $< g$) and the independence number $\alpha(G)$. Linearity of expectation gives $\mathbb{E}[X] = o(n)$, so by Markov $\mathbb{P}(X \geq n/2) \leq 1/2$ for large $n$; a direct estimate on the expected number of independent sets of size $s \sim n/(2k)$ gives $\mathbb{P}(\alpha(G) \geq s) \leq 1/2$. With positive probability both events fail, yielding a graph $G$ with $X < n/2$ and $\alpha(G) < n/(2k)$. Deleting one vertex from each short cycle produces a graph $\tilde{G}$ of girth at least $g$ with $|\tilde{G}| > n/2$ and $\alpha(\tilde{G}) \leq \alpha(G) < n/(2k)$. The bound [$\chi \geq |V|/\alpha$](/theorems/2055) then gives $\chi(\tilde{G}) > k$, as required. [/proofplan] [step:Set up the random graph model and target parameters] Fix integers $k, g \geq 3$. Choose a parameter $n \in \mathbb{N}$ (to be taken large) and let \begin{align*} p := n^{-1 + 1/g} \in (0, 1]. \end{align*} Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space carrying independent Bernoulli($p$) random variables $\mathbb{1}_{\{ij \in E(G)\}}$ for $1 \leq i < j \leq n$, defining the random graph $G \sim G(n, p)$ on vertex set $[n] = \{1, \ldots, n\}$. Note \begin{align*} np = n^{1/g}, \qquad np \to \infty \quad \text{as } n \to \infty. \end{align*} We will choose $n$ large enough to satisfy finitely many explicit conditions below and show that with positive probability the resulting $G$ can be modified to yield the desired graph. [/step] [step:Control the expected number of short cycles via Markov] For each integer $i \in \{3, \ldots, g-1\}$ let $X_i$ count the cycles of length $i$ in $G$, and set \begin{align*} X := X_3 + X_4 + \cdots + X_{g-1}. \end{align*} Fix $i \in \{3, \ldots, g-1\}$. The number of cycles of length $i$ on the labelled vertex set $[n]$ is at most $\frac{n!}{(n-i)! \cdot 2i}$ — there are $n(n-1) \cdots (n-i+1) \leq n^i$ ordered sequences of $i$ distinct vertices, each cycle admits $2i$ orderings (cyclic rotations and reflections), giving at most $n^i / (2i) \leq n^i / i$ cycles. Each cycle of length $i$ uses exactly $i$ edges, all of which are present in $G$ independently with probability $p$, so the indicator has expectation $p^i$. By [linearity of expectation](/theorems/???), \begin{align*} \mathbb{E}[X_i] \leq \frac{n^i}{i} \cdot p^i = \frac{(np)^i}{i} = \frac{n^{i/g}}{i}. \end{align*} Summing over $i = 3, \ldots, g - 1$, and using $1/i \leq 1$, \begin{align*} \mathbb{E}[X] \leq \sum_{i=3}^{g-1} n^{i/g} \leq (g - 3) \cdot n^{(g-1)/g}, \end{align*} because each summand is at most the largest one, $n^{(g-1)/g}$. Let $c := g - 3 \geq 0$; this is a constant depending only on $g$. By [Markov's inequality](/theorems/???) applied to the non-negative random variable $X$ with threshold $n/2$, \begin{align*} \mathbb{P}(X \geq n/2) \leq \frac{\mathbb{E}[X]}{n/2} \leq \frac{2c \cdot n^{(g-1)/g}}{n} = 2c \cdot n^{-1/g}. \end{align*} Since $(g - 1)/g < 1$, we have $n^{-1/g} \to 0$. Choose $N_1 = N_1(g) \in \mathbb{N}$ such that $2c \cdot n^{-1/g} \leq 1/2$ for all $n \geq N_1$. Then for $n \geq N_1$: \begin{align*} \mathbb{P}(X \geq n/2) \leq 1/2. \end{align*} [guided] We want to control the number of short cycles (cycles of length less than $g$). Once we control them in expectation and then by Markov in probability, the deletion argument in the last step will remove them. Define $X_i$ to be the number of cycles of length $i$ in $G$, for each $i \in \{3, \ldots, g-1\}$ — we need $i \geq 3$ since cycles have length $\geq 3$, and we only care about cycles below the target girth $g$. Set $X := X_3 + \cdots + X_{g-1}$, the total number of short cycles. To estimate $\mathbb{E}[X_i]$, we first count cycles. A cycle of length $i$ on labelled vertices $[n]$ can be specified by an ordered sequence $(v_1, \ldots, v_i)$ of distinct vertices, interpreted as the cyclic sequence $v_1 \to v_2 \to \cdots \to v_i \to v_1$. However, each cycle corresponds to $2i$ such sequences: $i$ rotations (starting from any of the $i$ vertices) $\times$ $2$ directions (forward or backward). The number of ordered distinct-vertex sequences is $n(n-1) \cdots (n-i+1) \leq n^i$, so the number of cycles is at most $n^i/(2i) \leq n^i/i$. Each cycle of length $i$ uses $i$ specific edges, and each edge is in $G$ independently with probability $p$, so a fixed cycle is contained in $G$ with probability $p^i$. By [linearity of expectation](/theorems/???), \begin{align*} \mathbb{E}[X_i] \leq \frac{n^i}{i} p^i = \frac{(np)^i}{i}. \end{align*} With $np = n^{1/g}$, each term is $n^{i/g}/i$. Summing for $i = 3, \ldots, g-1$ and bounding each summand by the largest, $n^{(g-1)/g}$: \begin{align*} \mathbb{E}[X] \leq \sum_{i=3}^{g-1} n^{i/g} \leq (g - 3) n^{(g-1)/g} =: c \cdot n^{(g-1)/g}, \end{align*} where $c = g - 3$ depends only on $g$. Now we apply [Markov](/theorems/???) with threshold $n/2$: \begin{align*} \mathbb{P}(X \geq n/2) \leq \frac{\mathbb{E}[X]}{n/2} \leq \frac{2c \cdot n^{(g-1)/g}}{n} = 2c \cdot n^{-1/g} \to 0 \quad \text{as } n \to \infty. \end{align*} The crucial point is that $(g-1)/g < 1$, so the expected number of short cycles is of order $n^{(g-1)/g} = o(n)$. Consequently, for all sufficiently large $n$ — say $n \geq N_1(g)$ with $2c \cdot N_1^{-1/g} \leq 1/2$ — we have $\mathbb{P}(X \geq n/2) \leq 1/2$. [/guided] [/step] [step:Control the independence number via a moment estimate on large independent sets] Set $s := \lceil n / (2k) \rceil \in \mathbb{N}$. Let $Y$ count the independent sets of size exactly $s$ in $G$: \begin{align*} Y := \sum_{\substack{S \subseteq [n] \\ |S| = s}} \mathbb{1}_{\{S \text{ independent in } G\}}. \end{align*} For a fixed $S$ with $|S| = s$, the event "$S$ is independent" requires none of the $\binom{s}{2}$ potential edges within $S$ to be present, so its probability is $(1 - p)^{\binom{s}{2}}$. By linearity of expectation, \begin{align*} \mathbb{E}[Y] = \binom{n}{s} (1-p)^{\binom{s}{2}}. \end{align*} Using $\binom{n}{s} \leq n^s$ and $1 - p \leq e^{-p}$, we get \begin{align*} \mathbb{E}[Y] \leq n^s e^{-p \binom{s}{2}}. \end{align*} Since $\binom{s}{2} = s(s-1)/2 \geq s^2/4$ for $s \geq 2$ (which holds provided $n \geq 2k - 1$ so that $s \geq 1$, and $s \geq 2$ once $n \geq 2k$; we later impose $n$ large enough), \begin{align*} \mathbb{E}[Y] \leq n^s e^{-p s^2 / 4} = \left(n \cdot e^{-ps/4}\right)^s. \end{align*} We show the base $n \cdot e^{-ps/4}$ tends to $0$ as $n \to \infty$. Since $s \geq n/(2k)$ and $p = n^{-1+1/g}$, \begin{align*} p s \geq \frac{n^{-1+1/g} \cdot n}{2k} = \frac{n^{1/g}}{2k} \to \infty, \end{align*} hence $e^{-ps/4} \to 0$ super-polynomially (faster than any power of $n$), so $n \cdot e^{-ps/4} \to 0$. In particular there exists $N_2 = N_2(k, g) \in \mathbb{N}$ such that for all $n \geq N_2$: \begin{align*} n \cdot e^{-ps/4} \leq \frac{1}{2}, \quad \text{so} \quad \mathbb{E}[Y] \leq 2^{-s} \leq \frac{1}{2}, \end{align*} where we used $s \geq 1$ for the last inequality. Then by [Markov](/theorems/???) with threshold $1$ applied to the non-negative integer-valued $Y$, \begin{align*} \mathbb{P}(\alpha(G) \geq s) = \mathbb{P}(Y \geq 1) \leq \mathbb{E}[Y] \leq \frac{1}{2}. \end{align*} [guided] To make $\chi(G)$ large, we will use the [inequality $\chi(G) \geq |G|/\alpha(G)$](/theorems/2055). This forces us to bound $\alpha(G)$ from above. We fix a target threshold $s := \lceil n/(2k) \rceil$ — this is the size such that $\alpha(G) < s$ will give $\chi \geq |G|/s > k$ after the forthcoming deletion reduces $|G|$ by at most half. Introduce the random variable $Y$ counting the independent sets of size exactly $s$ in $G$. Note $\{\alpha(G) \geq s\}$ is the event that *some* independent set of size $s$ exists, which is contained in $\{Y \geq 1\}$. Hence by [Markov](/theorems/???), \begin{align*} \mathbb{P}(\alpha(G) \geq s) \leq \mathbb{P}(Y \geq 1) \leq \mathbb{E}[Y]. \end{align*} To estimate $\mathbb{E}[Y]$: a fixed size-$s$ vertex set $S \subseteq [n]$ is independent iff all $\binom{s}{2}$ potential edges inside $S$ are absent, which has probability $(1 - p)^{\binom{s}{2}}$ (by independence of edge indicators). Summing over all $\binom{n}{s}$ choices of $S$: \begin{align*} \mathbb{E}[Y] = \binom{n}{s} (1 - p)^{\binom{s}{2}}. \end{align*} We apply the two standard inequalities $\binom{n}{s} \leq n^s$ and $1 - p \leq e^{-p}$ (valid for $p \in [0, 1]$) to get \begin{align*} \mathbb{E}[Y] \leq n^s e^{-p \binom{s}{2}}. \end{align*} For $s \geq 2$ we have $\binom{s}{2} = s(s-1)/2 \geq s^2/4$ (since $s - 1 \geq s/2$), so \begin{align*} \mathbb{E}[Y] \leq n^s e^{-p s^2 / 4} = (n \cdot e^{-ps/4})^s. \end{align*} Now we examine the base. Since $s \geq n/(2k)$ and $p = n^{-1+1/g}$, \begin{align*} p s \geq n^{-1 + 1/g} \cdot \frac{n}{2k} = \frac{n^{1/g}}{2k}, \end{align*} which tends to $\infty$ as $n \to \infty$ (using $g \geq 3$ so $1/g > 0$). In particular, $e^{-ps/4}$ decays faster than any negative power of $n$, so $n \cdot e^{-ps/4} \to 0$. Pick $N_2 = N_2(k, g) \in \mathbb{N}$ such that $n \cdot e^{-ps/4} \leq 1/2$ for all $n \geq N_2$. Then for such $n$, $\mathbb{E}[Y] \leq (1/2)^s \leq 1/2$, and hence \begin{align*} \mathbb{P}(\alpha(G) \geq s) \leq \mathbb{E}[Y] \leq 1/2. \end{align*} [/guided] [/step] [step:Extract a deterministic graph satisfying both structural bounds] Set $N := \max\{N_1, N_2, 2k\}$ and assume $n \geq N$. By the [union bound](/theorems/???), \begin{align*} \mathbb{P}(X \geq n/2 \text{ or } \alpha(G) \geq s) \leq \mathbb{P}(X \geq n/2) + \mathbb{P}(\alpha(G) \geq s) \leq \tfrac{1}{2} + \tfrac{1}{2} = 1. \end{align*} This bound is only $\leq 1$, which is not useful — we need the complement event to have *positive* probability. To sharpen, apply [Markov](/theorems/???) with the tighter factor from Step 2: for $n \geq N_1$ we actually established $\mathbb{P}(X \geq n/2) \leq 2c \cdot n^{-1/g} < 1/2$ whenever $n$ is sufficiently large. Specifically, pick $N_1' \geq N_1$ such that $2c \cdot n^{-1/g} < 1/3$ for $n \geq N_1'$, and $N_2' \geq N_2$ such that the bound of Step 3 gives $\mathbb{E}[Y] < 1/3$ for $n \geq N_2'$. Then for $n \geq N := \max\{N_1', N_2', 2k\}$: \begin{align*} \mathbb{P}(X \geq n/2 \text{ or } \alpha(G) \geq s) \leq \tfrac{1}{3} + \tfrac{1}{3} = \tfrac{2}{3} < 1. \end{align*} Hence the complementary event has probability at least $1/3 > 0$: \begin{align*} \mathbb{P}\!\left( X < n/2 \text{ and } \alpha(G) < s \right) \geq 1/3. \end{align*} In particular, there exists a deterministic outcome $\omega^* \in \Omega$, and hence a concrete graph $G^* := G(\omega^*)$ on $[n]$, satisfying \begin{align*} X(G^*) < n/2, \qquad \alpha(G^*) < s = \lceil n / (2k) \rceil. \end{align*} [guided] We now combine the two probabilistic bounds. Naively applying the [union bound](/theorems/???) with $1/2 + 1/2 = 1$ gives no room — both events could fail simultaneously with probability zero. We need both probabilities strictly below $1/2$. This is easy: each bound of the previous two steps is actually $o(1)$, not just $\leq 1/2$. Specifically, re-examining Step 2: $\mathbb{P}(X \geq n/2) \leq 2c \cdot n^{-1/g} \to 0$, so we may choose $N_1' \geq N_1$ with $2c \cdot n^{-1/g} < 1/3$ for $n \geq N_1'$. Re-examining Step 3: $\mathbb{E}[Y] \leq (n e^{-ps/4})^s$, and both the base $n e^{-ps/4}$ and exponent $s \geq n/(2k) \to \infty$ drive this to zero, so $\mathbb{E}[Y] < 1/3$ for all $n$ beyond some $N_2'$. For $n \geq N := \max\{N_1', N_2', 2k\}$, the union bound yields \begin{align*} \mathbb{P}(X \geq n/2 \text{ or } \alpha(G) \geq s) \leq \tfrac{1}{3} + \tfrac{1}{3} = \tfrac{2}{3}, \end{align*} so the complementary event has probability at least $1/3 > 0$. Since the probability is positive, there must exist some outcome $\omega^* \in \Omega$ — equivalently a concrete graph $G^* = G(\omega^*)$ — for which both conditions hold: \begin{align*} X(G^*) < n/2 \quad \text{and} \quad \alpha(G^*) < s. \end{align*} This is the probabilistic existence proof: we did not construct $G^*$ explicitly but demonstrated that some realisation of the random graph has the two structural properties simultaneously. We now fix such a $G^*$ and treat it as a deterministic graph for the remainder of the proof. [/guided] [/step] [step:Delete one vertex per short cycle to boost the girth] Let $\mathcal{C} := \{C : C \text{ is a cycle of length } < g \text{ in } G^*\}$. By the previous step, $|\mathcal{C}| = X(G^*) < n/2$. For each $C \in \mathcal{C}$ choose a distinguished vertex $v_C \in V(C)$ (any choice will do, say the vertex with the smallest label). Let \begin{align*} D := \{v_C : C \in \mathcal{C}\} \subseteq [n], \qquad |D| \leq |\mathcal{C}| < n/2. \end{align*} Define $\tilde{G} := G^* - D$, the induced subgraph on $V(G^*) \setminus D$. We verify three properties of $\tilde{G}$: (i) *Vertex count:* $|\tilde{G}| = n - |D| > n - n/2 = n/2$. (ii) *Girth:* Every cycle of length $< g$ in $G^*$ contains at least one vertex of $D$ (namely its own distinguished vertex $v_C \in D$) and is therefore destroyed by passing to $\tilde{G}$. Any cycle in $\tilde{G}$ is a cycle in $G^*$ lying entirely outside $D$, and hence has length $\geq g$. Thus $\operatorname{girth}(\tilde{G}) \geq g$ (where we interpret "no cycles" as girth $= \infty \geq g$). (iii) *Independence number:* Any independent set in $\tilde{G}$ is also an independent set in $G^*$ (the induced subgraph has fewer edges but the independence condition transfers), so $\alpha(\tilde{G}) \leq \alpha(G^*) < s = \lceil n/(2k) \rceil \leq n/(2k) + 1$. For $n \geq 2k$ we have $\lceil n/(2k) \rceil \leq n/k$ but we use the cleaner form $\alpha(\tilde{G}) \leq s$. [claim:$\alpha(\tilde{G}) \leq n/(2k)$ for $n$ a multiple of $2k$] If $n$ is a multiple of $2k$, then $s = n/(2k)$ exactly, and $\alpha(\tilde{G}) < s$ gives $\alpha(\tilde{G}) \leq s - 1 < n/(2k)$. For general $n \geq 2k$, $\alpha(\tilde{G}) < \lceil n/(2k) \rceil$, equivalently $\alpha(\tilde{G}) \leq \lceil n/(2k) \rceil - 1$. [proof] This follows from the integer inequality $\alpha < s$ for integer $\alpha$ and integer $s$. [/proof] [/claim] [/step] [step:Apply the $\chi \geq |V|/\alpha$ bound and conclude] We apply the [chromatic number vs independence number bound](/theorems/2055): for any graph $H$, \begin{align*} \chi(H) \geq \frac{|H|}{\alpha(H)}. \end{align*} Taking $H = \tilde{G}$ and using (i) and (iii) from the previous step, \begin{align*} \chi(\tilde{G}) \geq \frac{|\tilde{G}|}{\alpha(\tilde{G})} > \frac{n/2}{\lceil n/(2k) \rceil}. \end{align*} To bound the right-hand side from below by $k$, use $\lceil n/(2k) \rceil \leq n/(2k) + 1$, so \begin{align*} \frac{n/2}{\lceil n/(2k) \rceil} \geq \frac{n/2}{n/(2k) + 1} = \frac{n/2}{(n + 2k)/(2k)} = \frac{kn}{n + 2k} = k \cdot \frac{n}{n + 2k}. \end{align*} Choose $N' \geq N$ such that $n/(n + 2k) > (k - 1)/k$ for $n \geq N'$; solving, this requires $n > 2k(k-1)$. For $n \geq \max\{N, 2k(k-1) + 1\}$ we get $k \cdot n/(n + 2k) > k - 1$, and since $\chi(\tilde{G})$ is an integer strictly greater than $k - 1$, we have $\chi(\tilde{G}) \geq k$. Combining with (ii), $\tilde{G}$ is a graph with $\operatorname{girth}(\tilde{G}) \geq g$ and $\chi(\tilde{G}) \geq k$. This completes the proof. [guided] The final step is to convert the structural bounds on $\tilde{G}$ into the chromatic-number lower bound. We apply the [chromatic number vs independence number inequality](/theorems/2055): for any graph $H$, \begin{align*} \chi(H) \geq \frac{|H|}{\alpha(H)}. \end{align*} Taking $H = \tilde{G}$ and using $|\tilde{G}| > n/2$ and $\alpha(\tilde{G}) < \lceil n/(2k) \rceil$: \begin{align*} \chi(\tilde{G}) \geq \frac{|\tilde{G}|}{\alpha(\tilde{G})} > \frac{n/2}{\lceil n/(2k) \rceil}. \end{align*} We want to show this exceeds $k - 1$ (so that $\chi(\tilde{G}) \geq k$, as $\chi$ is an integer). The ceiling gives $\lceil n/(2k) \rceil \leq n/(2k) + 1$, so \begin{align*} \frac{n/2}{\lceil n/(2k) \rceil} \geq \frac{n/2}{n/(2k) + 1} = \frac{n/2}{(n + 2k)/(2k)} = \frac{kn}{n + 2k} = k \cdot \frac{n}{n + 2k}. \end{align*} We now need $k \cdot \frac{n}{n + 2k} > k - 1$, equivalently $\frac{n}{n + 2k} > \frac{k-1}{k}$, equivalently $kn > (k-1)(n + 2k) = kn - n + 2k^2 - 2k$, equivalently $n > 2k^2 - 2k = 2k(k-1)$. So for $n \geq 2k(k-1) + 1$ (and $n \geq N$ from Step 4) we have $\chi(\tilde{G}) > k - 1$, and since $\chi(\tilde{G}) \in \mathbb{N}$ this means $\chi(\tilde{G}) \geq k$. Choosing $n \geq \max\{N, 2k(k-1) + 1\}$ and running through Steps 1--5 produces a deterministic graph $\tilde{G}$ with \begin{align*} \operatorname{girth}(\tilde{G}) \geq g \qquad \text{and} \qquad \chi(\tilde{G}) \geq k, \end{align*} as required. The existence of such an $n$ is automatic — it is a single numerical condition depending only on $k$ and $g$ — and this completes the proof. The proof illustrates the power of probabilistic existence: the theorem is a constructive-sounding statement ("there exists a graph with these two competing properties"), but no natural explicit construction was known at the time of Erdős's 1959 paper. The random graph provides the existence; the deletion step cleans up the short cycles that an unweighted random sample inevitably contains. [/guided] [/step]