Let $\Gamma$ be a graph with no cycles of odd length, loops, multiple edges and such that $4e > (v-1)^2$ where $v$ is the number of vertices and $e$ of edges.
How to prove that $\Gamma$ is connected?
I see that it's bipartite but have no idea how to use it.
In the following for $x \in \mathbb{R}$ we denote by $\lceil x\rceil$ the smallest integer $m$ such that $m \geq x$, similarly by $\lfloor x \rfloor$ we denote the largest integer $m$ such that $m \leq x$.
I leave the following two statements as exercises for you to prove:
Exercise 1: A bipartite graph on $v$ vertices has at most $\lceil v/2 \rceil \lfloor v/2 \rfloor$ edges.
Exercise 2: The function $(v_1,v_2) \mapsto \lceil v_1/2 \rceil \lfloor v_1/2 \rfloor + \lceil v_2/2 \rceil \lfloor v_2/2 \rfloor$ subject to the constraints that $v_1,v_2 \geq 1$ are integers and $v_1 + v_2 = v$ has maximium $\lceil (v-1)/2 \rceil \lfloor (v-1)/2 \rfloor$.
Given these two results the statement can be proved as follows:
For a graph $\Gamma = (V,E)$ and a subset $W \subseteq V$ we denote by $\Gamma[W]$ the induced subgraph of $\Gamma$ obtained from $\Gamma$ by deleting all vertices which are not in $W$ and all edges which have an endpoint that is not in $W$.
Assume for the sake of contradiction that $\Gamma = (V,E)$ is not connected, then there is a partition of the vertex set $V = V_1 \dot\cup V_2$, where $|V_1| = v_1$ and $|V_2| = v_2$ such that neither $V_1$ nor $V_2$ is empty and there is no edge in $\Gamma$ going from $V_1$ to $V_2$. Thus the number of edges in $\Gamma$ is the number of edges in $\Gamma[V_1]$ plus the number of edges in $\Gamma[V_2]$. Further $\Gamma[V_1]$ and $\Gamma[V_2]$ are bipartite (as subgraphs of a bipartite graph). Hence by Exercise 1 and Exercise 2 we have $$ e \leq \lceil v_1/2 \rceil \lfloor v_1/2 \rfloor + \lceil v_2/2 \rceil \lfloor v_2/2 \rfloor \leq \lceil (v-1)/2 \rceil \lfloor (v-1)/2 \rfloor \leq ((v-1)/2)^2. $$ Further by assumption we have $e > ((v-1)/2)^2$, thus $$ ((v-1)/2)^2 < e \leq ((v-1)/2)^2, $$ which is a contradiction. Hence $\Gamma$ must be connected.