Mainstream semi-supervised classification assumes that part of the available data are labelled. Here we assume that, in addition to the labels, we have pairwise constraints on the unlabelled data. Each constraint links two instances, and is one of Must Link (ML, belong to the same class) or Cannot Link (CL, belong to different classes). We propose an approach that uses the labelled data to train a classifier and then applies the ML and CL constraints in subsequent labelling. In our approach, a set of instances are labelled at the same time. Our case study is on animal re-identification. The dataset consists of five free-camera video clips of of animals (koi fish, pigeons and pigs), annotated with bounding boxes and animal identities. The proposed approach combines the representations or classifiers predictions from the bounding boxes of consecutive frames. We demonstrate that our approach outperforms standard classifiers, constrained clustering, as well as inductive and transductive semi-supervised learning, using five feature representations.