In Diestel's Graph Theory, I try to figure out the proof of Theorem 11.2.2 on page 301:
given any positive integer $k$, there is a graph $G$ with girth $g(G)>k$ (that is the length of the shortest cycle in graph $G$) and $\chi(G)>k$ (the smallest number of colors so that each pair of adjacent vertices with different colors).
I have one question about the proof. In the following proof, let $X$ be the number of short cycles (length of cycles is at most $k$) in a random graph $G \in \mathcal{G}(n,p)$. We show that
$$ P(X\ge \frac{n}{2})\le \frac{1}{2} $$ as $n$ large enough. This means the number of short cycles greater than $n/2$ with high probability.
Also, choose $p=n^{\epsilon-1}$ and $n$ large enough that we have the size of independent vertices $\alpha(G)$ $$ P(\alpha(G)\ge \frac{1}{2}\frac{n}{k})<\frac{1}{2}. $$ This means the size of the largest independent set of vertices cannot be too large with high probability.
Question: Why can we then say that there is a graph $G\in \mathcal{g}(n,p)$ with fewer than $n/2$ short cycles and $\alpha(G)< \frac{1}{2}\frac{n}{k}$ independent vertices?
I think this event holds with high probability. Why not say "high probability"? For me, there is a certain probability that I will not find such a figure, but the probability is very small.
This is basically the simple inclusion-exclusion formula: $$P(A\cup B) = P(A)+P(B)-P(A\cap B)$$ In your case, taking $A=X<n/2$ and $B=\alpha < \frac{1}{2}n/k$ shows that $P(A\cap B) > 0$ since the LHS is at most $1$ while $P(A)+P(B)>1$.