If we have a subgroup of index 3 that is not normal, show there is a subgroup with index 2 
Given a a subgroup $H$ of $G$ with index $3$, we have to show there is a subgroup $K$ of $G$ with index $2$, assuming that $H$ is not a normal subgroup of $G$.

My line of thinking was the following:
So $[G:H]=3$ and $H$ is not normal. This means there is a smaller prime which can divide $G$, thus, $2$ divides $G$. We then use Cauchy's theorem to say that there is an element $g$ in $G$ with order $2$.
Will it work to then use the permutation representation of left multiplication on $G$ and the existence of an odd permutation?
Any hint in the right direction will be much appreciated. Thanks.
 A: Let $G$ act on the cosets of $H$, we obtain a morphism $G \to S_3$ with Kernel $N$. It is well known that we have $N \leq H$. Since $H$ is not normal, $G \to S_3$ is surjective, because the image has more than $3$ elements. By the sign we obtain a surjection $G \to S_3 \to \{-1,1\}$, hence a subgroup of index $2$.
A: Hint: The action of $G$ on the left cosets of $H$ via left multiplication gives a homomorphism:
$\phi: G \rightarrow S_{3}$. The $\ker \phi$ is the largest normal subgroup contained in $H$. Now consider $\frac{|G|}{|\ker \phi | } = \frac{3|H|}{|\ker \phi |} \in \{1, 2, 3, 6 \}$. Use the fact that $|\ker \phi|$ divides $|H|$, that $2$ does not divide $3$ and the fact that $H$ is not normal to deduce that $G$ would be $S_{3}$ which has a subgroup of index 2. 
A: In general: Proposition If $p$ is the smallest prime dividing the order of a group $G$, then a subgroup of index $p$ is normal in $G$. The proof of this fact is along the same reasoning as the others here on this page: if $H$ is a subgroup of index $p$ let $G$ act on the right cosets of $H$ by right multiplication. The kernel of this action, called $core_G(H)$, is a normal subgroup of $G$ contained in $H$. Then $G/core_G(H)$ embeds homomorphically into $S_p$. And the order of $S_p$ is $p \cdot (p-1) \cdots 2 \cdot 1$.
Note (see remark of Marc van Leeuwen below, which is totally justified). I misread the OP post. Let's proceed along the lines of my reasoning above: we have $core_G(H) \subsetneq H \subsetneq G$. The first inclusion is strict, since $H$ is not normal. Since $G/core_G(H)$ embeds homomorphically into $S_3$, it follows that in fact $G/core_G(H) \cong S_3$. Since $A_3$ has index 2 in $S_3$, there has to be a subgroup $K$ of $G$, such that $core_G(H) \subseteq K$ and $K/core_G(H) \cong A_3$. But then index$[G:K]=2$.
