This is a technical report, containing all the theorem proofs in paper Node Failure Localization in Communication Networks via Network Tomography by Liang Ma, Ting He, Ananthram Swami, Don Towsley, Kin K. Leung, and Jessica Lowe, published in ITA Annual Fall Meeting, 2014.