Suppose that the graph has exactly 14 edges. Prove that it contains a Hamilton Cycle.
I thought of going in the direction of saying it is a bipartite graph which means since the amount of blue and red nodes are the same, it contains a hamilton cycle but I am not sure if that is the way to prove this. Am I supposed to use dirac's or ore's theorem instead? I am not sure.
I suppose you know that $K_{n,n}$ has a Hamiltonian cycle (if $n\ge2$). The graph $K_{n,n}$ has $n^2$ edges and the Hamiltonian cycle has $2n$ edges, so it misses $n^2-2n$ edges. Since $n\ge4$, we have $n^2-2n\gt n$, so there are at least $n+1$ missing edges, among which must be a pair of adjacent edges, and a pair of nonadjacent edges. Under the automorphism group of $K_{n,n}$, any pair of adjacent edges is similar to any other, and any pair of nonadjacent edges is similar to any other. Therefore, any two given edges of $K_{n,n}$ can be avoided by a Hamiltonian cycle.
Alternatively, withoug all that algebra: $C$ is a Hamiltoniam cycle in $K_{n,n}$; we have to show that $C$ misses a pair of adjacent edges of $K_{n,n}$ and a pair of nonadjacent edges of $K_{n,n}$.
Take a red vertex $r$. Since $r$ has just $2$ neighbors in $C$, and since there are at least $4$ blue vertices, there are at least two blue vertices $b_1,b_2$ which are not neighbors of $r$, so $rb_1$ and $rb_2$ are two adjacent vertices of $K_{n,n}$ which are avoided by $C$.
Take two red vertices $r_1$ and $r_2$. Each of them has $2$ blue neighbors in $C$, but they can't be the same two neighbors, since $n\gt2$. So $r_1$ has a neighbor $b_1$ which is not a neighbor of $r_2$, and $r_2$ has a neighbor $b_2$ which is not a neighbor of $r_1$. Then $r_1b_2$ and $r_2b_2$ are nonadjecent vertices of $K_{n,n}$ which are avoided by $C$.