A theorem due to Youngs (1963) says that any minimal genus embedding is necessarily a $2$-cell embedding, i.e., every face is homeomorphic to a disc.
Suppose, for the sake of contradiction that, the given embedding of $G$ into $Q$ is a minimal genus embedding of $G$.
Let $G_L$ and $G_R$ be the unions of the left and right components, respectively, of $G - C$.
Case 1: At least one of $G_L$ or $G_R$ is empty.
- Suppose, without loss of generality, that $G_L$ is empty.
Consider the face of $G$ that contains $C$ and intersects the left of $C$.
By Youngs's theorem, this face must be homeomorphic to a disc.
But, $C$ is not contractible (else it would separate the surface $Q$ into two components).
Hence, a small leftward shift of $C$ — which will lie in the face $f$ — will also not be contractible.
This contradicts that $f$ is homeomorphic to a disc, since a disc is simply connected.
Case 2: Both $G_L$ and $G_R$ are nonempty.
We first show that if a face contains vertices of $G_L$ and of $C$ (resp., of $G_R$ and of $C$), then it cannot contain vertices of $G_R$ (resp, of $G_L$).
Suppose, for the sake of contradiction, that there is such a face $f$ of degree $d$.
Let $\partial f = v_0 \dotsm v_{d-1}$ be the boundary cycle of $f$, where $i \in \mathbb{Z}/d \mathbb{Z}$.
Without loss of generality, assume that $v_0 \in C$, and $v_{d-1} \notin C$.
Then, we can also express the boundary as $\partial f = P_1 \dotsm P_{k}$ for some $k$, where each $P_i$ is a maximal subpath of the boundary that is contained in $G_L$ or $G_R$ or $C$.
Note that every alternate $P_i$ must be contained in $C$, by assumption 3 (in particular, $k$ is even).
Denote by $v_L(P_i)$ and $v_R(P_i)$ the left- and right-end vertices, respectively, of the path $P_i$.
Now, $\mathrm{Int}(f)$ intersects a small neighborhood of $v_0 = v_L(P_1)$ in either the left of $C$ or the right of $C$.
Without loss of generality, assume that it intersects the left of $C$.
Then, $\mathrm{Int}(f)$ also intersects the left of a small neighborhood of $v_i$, for each $v_i \in P_1$.
Hence, $v_L(P_2)$ must belong to $G_L$, since the edge joining $v_L(P_2)$ to $v_R(P_1)$ intersects the left of $C$ near $v_R(P_1)$.
(We can also do a similar analysis at the other end of $P_1$. So, $v_R(P_{k})$ must belong to $G_L$, since the edge joining $v_R(P_{k})$ to $v_L(P_1) = v_0$ intersects the left of $C$ near $v_0$.)
Since $v_L(P_2)$ belongs to $G_L$, so does every vertex $v_i \in P_2$.
Therefore, the edge joining $v_R(P_2)$ to $v_L(P_3)$ must also intersect the left of $C$ near $v_L(P_3)$.
Otherwise, an argument as in the parenthetical remark above will show that $v_R(P_2)$ belongs to $G_R$, which is not possible.
Thus, proceeding inductively, we conclude that if $\partial f$ contains vertices of $C$ and $G_L$, then it cannot contain any vertices of $G_R$.
Next, we show that if there is a face of $G$ that contains vertices of $G_L$ and of $G_R$ (but not of $C$), then we again arrive at a contradiction:
the boundary of such a face $f$ will necessarily contain more than one connected component, since there can be no edge between vertices of $G_L$ and of $G_R$.
But, this is not possible since $f$ is homeomorphic to a disc by Youngs's theorem.
Now, consider the subsets $Q_L$ and $Q_R$ of $Q$ obtained by taking the union of all the vertices, edges and faces induced by $G_L \cup C$ and $G_R \cup C$, respectively.
By assumption 3, every component of $G - C$ is in $G_L$ or $G_R$, so every vertex and edge of $G$ belongs to $Q_L$ or $Q_R$.
By the subcases eliminated above under Case 2, every face of $G$ also belongs to $Q_L$ or $Q_R$ (but not both).
Then, $Q = Q_L \cup Q_R = (Q_L - C) \sqcup (Q_R - C) \sqcup C$.
This means that $C$ separates $Q$ into two components, which contradicts assumption 1.
References
Youngs, J. W. T., Minimal imbeddings and the genus of a graph, J. Math. Mech. 12, 303–315 (1963). Zbl 0109.41701, Zbl 0213.26001.
