Finding subgroups of a free group with a specific index

How many subgroups with index two are there of a free group on two generators? What are their generators?

All I know is that the subgroups should have $(2 \times 2) + 1 - 2 = 3$ generators.

Mariano's answer is quite right, but relies on the 'accident' that all subgroups of index two are normal. If you wanted to find all the subgroups of index three, say, you would need to try another approach. Here's one idea.

The free group of rank two, $F$, is the fundamental group of the figure-eight graph $\Gamma$, which has one vertex and two edges. Fix the vertex as the base point. The subgroups of index $k$ correspond, via covering-space theory, to connected covering spaces $\widehat{\Gamma}\to\Gamma$ of degree $k$, with a choice of base vertex $\hat{v}\in\widehat{\Gamma}$. (If, on the other hand, you only wanted to count conjugacy classes of subgroups, you could forget about $\hat{v}$.) Because the covering map $p:\widehat{\Gamma}\to\Gamma$ has degree $k$, the graph $\widehat{\Gamma}$ has exactly $k$ vertices.

Let's decorate the graph $\Gamma$ so that we can see $F=\langle a,b\rangle$ more clearly. Label each edge with the corresponding generator $a$ or $b$. Furthermore, orient each edge to indicate in which direction the generator goes around it.

You can use the covering map $p$ to pull the labels and orientations back from $\Gamma$ to $\widehat{\Gamma}$. That is, if $\hat{e}$ is an edge of $\widehat{\Gamma}$ and $p(\hat{e})=e$ is labelled $a$, then you should label $\hat{e}$ with $a$ also, and orient $\hat{e}$ so that $p$ sends the orientation on $\hat{e}$ to the orientation on $e$.

With a little thought, it's not too hard to see that this decoration on $\widehat{\Gamma}$---the labels and orientation---are enough to reconstruct the map $p$: they tell you where to send each edge, and there's only one choice of where to send each vertex. The statement that $p$ is a covering map translates into a nice condition on the decoration of $\widehat{\Gamma}$: for each vertex $\hat{u}$, you see exactly one edge with label going into $\hat{u}$, and exactly one edge with each label going out of $\hat{u}$. I'll call this condition 'the covering condition'.

This discussion turns counting the subgroups of index $k$ into the combinatorial problem of counting the connected, decorated, based graphs $\widehat{\Gamma}$ with $k$ vertices that satisfy the covering condition. With a little thought, one can write down a formula for this. Marshall Hall Jr did just this (though I don't think he thought in terms of the covering spaces of graphs) and came up with the following formula. Let $N(k,r)$ be the number of subgroups of index $k$ in the free group of rank $r$. Then

$N(k,r)=k(k!)^{r-1}-\sum_{i=1}^{k-1}((k-i)!)^{r-1}N(i,r)$.

For some related things, I wrote a blog post about proving theorems about free groups by thinking about covering spaces of graphs here.

Alternatively, if you don't like covering spaces, an equivalent point of view is to count transitive actions by permutation groups with $r$ generators on based sets of size $k$. This turns out to be the same combinatorial problem.

Let $F$ be free on $a$ and $b$, and let $N$ be a subgroup of index $2$. Then $N$ is normal, and there is a map $\phi:F\to\mathbb Z/2\mathbb Z$ with kernel precisely $N$. What are the possible images of $a$ and $b$? For each possible choice you can describe the corresponding generators of $N$ as a normal subgroup, and with a little extra work, generators as subgroup.

I like to approach this sort of problem using graphs. The free group on two generators is the fundamental group of a wedge of two circles $R_2$, which I picture as a red oriented circle and a black oriented circle. A subgroup of index $ k$ corresponds to a covering map $G\to R_2$ of index $k$. $G$ can be pictured as a (Edit: basepointed) $k$-vertex connected graph with red and black oriented edges such that at every vertex there is one incoming and one outgoing edge of each color. In the case $k=2$, it's not hard to write down all such graphs. I count three myself.