Q1: A Completely Odd Cycle

Disclaimer: This is not original, but it is in my wording!

Step 1: Bounding

Claim: For $n$ colours, $2^n+1$ vertices are sufficient.

We will use induction. The base case for $n=1$ is trivial, as you will have $3$ vertices joined by edges all of the same colour.

Now for the induction. Assume that the statement is true for a certain $n$ colours. Now consider the case of $n+1$ colours. Suppose for a contradiction that no odd cycles of one colour, red say, exist; i.e. all red cycles have an even number of vertices.

We claim that it is possible to split all the vertices into two (disjoint) sets, where in each set, no pair of vertices is joined by a red edge. Indeed, this is the trick for even cycles of this problem:

For each red cycle, start at one vertex and place it in one set. Then move to the next vertex in the cycle and place it in the other set. Continue doing this until all vertices are placed.

This works because each red cycle has an even number of vertices (from the supposition)! Furthermore, each vertex is definitely in one of the sets because every vertex is part of a cycle (minimum length is 2, where two vertices are joined by a red edge). As for the vertices with no red edges attached to them, they can go in either set without any effect.

Since we have $2^{n+1}+1$ vertices, one of the sets must have at least $2^n+1$ vertices. But in this set, vertices are only connected by $n$ colours, as none are connected by a red edge! So from the induction assumption, this set must contain an odd cycle of only one colour, and so the induction is done.

Step 2: Achievability

Now we must show the existence of a graph not satisfying the conditions with $2^n$ vertices (or less, but having found this graph, we can take any subgraph of the desired number of vertices).

This, in my opinion, is a really beautiful construction indeed. Number the vertices from $0$ to $2^n-1$ and consider their binary representation as a $n$ digit number (e.g. $1$ is $00000001$ if $n=8$ ). Now between any two vertices, with number $m$ and $n$ say, colour their connecting edge with the $k$ th colour where $m$ and $n$ have their first $k-1$ digits the same, but their $k$ th digit is different.

There are no odd cycles of one colour here! That is because all cycles of the $k$ th colour are even, because the $k$ th digit alternates from $0$ to $1$ !

Therefore the answer is $\boxed{2049}$ .