To understand how the brain is wired calls for investigating how the brain's wiring information (the connectome) is encoded in the genome. From small insects to humans, the apparent complexity of biological neural networks, in particular the information amount required to describe all connections in the connectome, far exceeds the genomic storage capacity. To explain the discrepancy in information volume between a direct description of the brain network and the coding genome's size, an emerging hypothesis, coined the genomic bottleneck principle, proposes that the wiring information must be compressed within the genome. Across diverse model animals, experiments both at the level of single neurons and of neural populations support this assumption, based on the observation of stereotyped “canonical” microcircuits. Such regular structural patterns throughout connectomes are hypothesized to have core roles in a wide range of biological functions. Information theory furthermore tells us that the presence of such statistically significant circuits, termed motifs, makes a compressed representation of the brain's wiring diagram possible. To test the genomic bottleneck and canonical microcircuits hypotheses, we relied on recent connectomic data acquired at single synapses resolution from whole-CNS EM volumes in Drosophila melanogaster. We developed lossless network compression techniques based on subgraph contractions and subgraph covers that allowed us to mine small network motifs and select the combination of motifs that maximally compresses a connectome with respect to a hierarchy of random graph null models such as Erdős-Rényi graphs or the configuration model. Our compression-based analysis circumvents problems related to multiple testing encountered when mining motifs individually using null hypothesis testing. Our results demonstrate the compressibility of neural connectomes and lend support to the canonical circuit hypothesis at the scale of single neurons, though with circuit motifs that may depend on brain region.