Back-propagation through max pooling layers
If this is correct then every "neuron" of the pooling layer has the same gradient?


No. It depends on the weights and activation function. And most typically the weights are different from the first neuron of the pooling layer to the FC layer as from the second layer of the pooling layer to the FC layer.

So typically you will have a situation like:

$ FC_i = f(\sum_j W_{ij} P_j)$

Where $FC_i$ is the ith neuron in the fully connected layer, $P_j$ is the jth neuron in the pooling layer and $f$ is the activation function and $W$ the weigths.

This means that the gradient with respect to P_j is 

$grad(P_j) = \sum_i grad(FC_i) f^\prime W_{ij}$.

Which is different for j=0 or j=1 because the W is different. 


  And the second question is when the pooling layer is connected to another convolution layer. How do I compute the gradient then?


It does not make a difference what type of layer it is connected to. It is the same equation all the time. Sum of all the gradients on the next layer multiplied by how the output of those neurons is affected by the neuron on the previous layer. The difference between FC and Convolution is that in FC all neurons in the next layer will provide a contribution (even if maybe small) but in Convolution most neurons in the next layer are not at all affected by the neuron in the previous layer so their contribution is exactly zero. 


  For the topmost rightmost "neuron" of the pooling layer (the outlined green one) I just take the gradient of the purple neuron in the next conv layer and route it back, right?


Right. Plus also the gradient of any other neurons on that convolution layer which take as input the topmost rightmost neuron of the pooling layer. 


  How about the filled green one? I need to multiply together the first column of neurons in the next layer because of the chain rule? Or do I need to add them?


Add them. Because of the chain rule. 

Max Pooling
Up to the this point, the fact that it was max pool was totally irrelevant as you can see. Max pooling is just the that the activation function on that layer is $max$. So this means that the gradients for the previous layers $grad(PR_j)$ are:

$grad(PR_j) = \sum_i grad(P_i) f^\prime W_{ij}$.

But now $f = id$ for the max neuron and $f = 0$ for all other neurons, so $f^\prime = 1$ for the max neuron in the previous layer and $f^\prime = 0$ for all other neurons. So:

$grad(PR_{max neuron}) = \sum_i grad(P_i) W_{i\ {max\ neuron}}$,

$grad(PR_{others}) = 0.$