Functional connectivity analysis of fMRI data can reveal synchronised activity between anatomically distinct brain regions. Here, we extract the characteristic connectivity signatures of different brain states to perform classification, allowing us to decode the different states based on the functional connectivity patterns. Our approach is based on polythetic decision trees, which combine powerful discriminative ability with interpretability of results. We also propose to use ensemble of classifiers within specific frequency subbands, and show that they bring systematic improvement in classification accuracy. Exploiting multi-band classification of connectivity graphs is also proposed, and we explain theoretical reasons why the technique could bring further improvement in classification performance. The choice of decision trees as classifier is shown to provide a practical way to identify a subset of connections that distinguishes best between the conditions, permitting the extraction of very compact representations for differences between brain states, which we call discriminative graphs. Our experimental results based on strict train/test separation at all stages of processing show that the method is applicable to inter-subject brain decoding with relatively low error rates for the task considered.