Functional connectivity analysis of fMRI data can reveal synchronized activity between anatomically distinct brain regions. Here, we exploit the characteristic connectivity graphs of task and resting epochs to perform classification between these conditions. Our approach is based on ensembles of decision trees, which combine powerful discriminative ability with interpretability of results. This makes it possible to extract discriminative graphs that represent a subset of the connections that distinguish best between the experimental conditions. Our experimental results also show that the method can be applied for group-level brain decoding.