Supplementary Material for Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities

Sections A - E prove our main results in detail. We next introduce some notation pertaining to the construction of the correlated SBMs. In this section we prove Theorem 3.1 in the main text. To make these ideas more formal, we begin by defining some notation. Remark B.2. Since our goal is to bound the probability of the event To apply Lemma B.3 later on, we need to compute/estimate This leads to the subtracted term in (5).