# IFDA: Intermittent Fault Diagnosis Algorithm for Augmented Cubes Under the PMC Model
## Appendix A
### _Proof of the Lemma 14_  
In \(AQ_{n}\)\((n\geq 4)\), for any node subcollection \(M\), as long as \(1\leq|M|\leq 2n-2\) always has \(\left|N_{AQ_{n}}(M)\right|\geq 2n-1\) holds. **Proof of Lemma 14**. Let us consider \(AQ_{4}\) first. Figure 1 illustrates \(AQ_{4}\), \(AQ_{4}=L\oplus R\), where \(L\cong AQ_{3}^{0}\) and \(R\cong AQ_{3}^{1}\). To prove Lemma 14, we need to prove that in \(AQ_{4}\), for any node subcollection \(M\), as long as \(1\leq|M|\leq 2\times 4-2=6\) always has \(\left|N_{AQ_{4}}(M)\right|\geq 2\times 4-1=7\) holds. **Case 1. ** There is only one node \(x\) in the set of \(M\), and we assume that \(x\in V_{L}\), by Property 1, we have that \(|N_{L}(x)|=2(n-1)-1=5\), \(|N_{R}(x)|=2\). Hence \(\left|N_{AQ_{4}}(M)\right|=|N_{L}(x)|+|N_{R}(x)|=5+2=7\) holds. **Case 2. ** There are two nodes \(x\) and \(y\) in the set of \(M\). By Lemma 4, we have that \(x\) and \(y\) are two arbitrary nodes in \(AQ_{4}\), then, \(\left|N_{AQ_{4}}(\{x,y\})\right|\geq 4n-8=8\) holds. **Case 3. ** There are three nodes \(x,y,z\) in the set of \(M\). **Case 3.1. ** We assume that the three nodes \(x,y,z\in V_{L}\). This can be seen from Figure 1, \(|N_{L}(\{x,y,z\})|\geq 5\). Because every node in \(L\) have two nodes in \(R\), however, for three nodes, there may be one common adjacent node that overlaps, so there will be at least \(2^{*}3-1=5\) nodes in \(R\). According to the characteristics of the augmented cubes, each node in \(L\) has a corresponding node in \(R\), and the two nodes form a hypercube pair. The complement pairs case is not considered. Hence, \(\left|N_{R}(\{x,y,z\})\right|\geq 3\). Hence \(\left|N_{AQ_{4}}(M)\right|\geq|N_{L}(\{x,y,z\})|+|N_{R}(\{x,y,z\})|=5+3=8\) holds. **Case 3.2. ** We assume that \(x,y\in V_{L},z\in V_{R}\). By Lemma 4, we have that \(|N_{L}(\{x,y\})|\geq 4(n-1)-8=4\). By Property 1, we have that \(|N_{R}(\{z\})|=2(n-1)-1=5\). As shown in Figure 1, \(\left|N_{AQ_{4}}(M)\right|\geq|N_{L}(\{x,y\})|+|N_{R}(z)|=4+5=9\) holds. **Case 4. ** There are four nodes \(x,y,z,s\) in the set of \(M\). By combining the above six cases, we complete the proof for \(AQ_{4}\). Now, we prove this lemma by induction on \(n+1\). The case for \(n=4\) has been demonstrated. Assume that the result holds for \(AQ_{n}\), where \(n\geq 4\). We now consider \(AQ_{n+1}=L\oplus R\), where \(L\cong AQ_{n}^{0}\) and \(R\cong AQ_{n}^{1}\). We need to prove that when \(1\leq|M|\leq 2\times(n+1)-2=2n\), then \(\left|N_{AQ_{n+1}}(M)\right|\geq 2\times(n+1)-1=2n+1\) holds. **Case 1. ** All of nodes in the set of \(M\) are in the same subcube. Without loss of generality, we assume that \(M\in V_{L}\). We have the following scenarios:  
**Case 1.1. **\(1\leq|M|\leq 2n-2\), \(M\in V_{L}\) (see Figure A2a). By the induction hypothesis, we have that \(\left|N_{L}(M)\right|\geq 2n-1\), \(\left|N_{R}(M)\right|\geq 2\) clearly holds. Hence, \(\left|N_{AQ_{n+1}}(M)\right|=\left|N_{L}(M)\right|+\left|N_{R}(M)\right|\geq (2n-1)+2=2n+1\) holds. **Case 1.2. **\(|M|=2n-1\), \(M\in V_{L}\). We assume that \(|M|=|M_{1}|+|M_{2}|\), there are \((2n-2)\) nodes in the set of \(M_{1}\), and there is only one node \(x\) in the set of \(M_{2}\) (see Figure A2b). By the induction hypothesis, we have that \(\left|N_{L}(M_{1})\right|\geq 2n-1\) and \(\left|N_{R}(x)\right|=2\). Clearly, \(\left|N_{AQ_{n+1}}(M)\right|\geq\left|N_{L}(M_{1})\right|+\left|N_{R}(x)\right| =2n+1\) holds. **Case 1.3. **\(|M|=2n\), \(M\in V_{L}\). We assume that \(|M|=|M_{1}|+|M_{2}|\), there are \((2n-2)\) nodes in the set of \(M_{1}\), and there are two nodes \(x\) and \(y\) in the set of \(M_{2}\). **Case 1.3.1. **\(L\) contains one complement pair among \(x\) and \(y\) (see Figure A2c). By the induction hypothesis, we have that \(\left|N_{L}(M_{1})\right|\geq 2n-1\). By Property 2, we have that \(\left|N_{R}(\{x,y\})\right|=2\). Clearly, \(\left|N_{AQ_{n+1}}(M)\right|\geq\left|N_{L}(M_{1})\right|+\left|N_{R}(\{x,y \})\right|=2n+1\) holds. **Case 1.3.2. ** There is no complement pair among \(x\) and \(y\) (see Figure A2d).