# A Set-Theoretic Approach to Modeling Network Structure
## 3 Network Properties
### Network Properties Preserved by the Interior  
The next three lemmas, culminating in Proposition 5, help clarify the interaction of \(\beta\)-sets with the nodes of \(\mathcal{I}\). In these lemmas, we assume that \(x_{0},y_{0}\) and \(z_{0}\in\mathcal{I}\).  
Lemma 1: _Let \(y_{k}\in\{y_{0}\}.\beta\). There exists a node sequence \(\langle y_{0},y_{1},\ldots,y_{k}\rangle\) such that \(y_{i}\in\{y_{0}\}.\beta\), \(0\leq i\leq k\)._  
Proof: In the reduction process of Pseudocode I, if \(y_{i+1}\) is subsumed by \(y_{i}\), then \(\{y_{i+1}\}.\beta\subset\{y_{i}\}.\beta\) yielding the chain of nested sets \(\{y_{k}\}.\beta\subset\{y_{k-1}\}.\beta\subset\ldots\subset\{y_{0}\}.\beta\).  
Note that, even if \(y_{i}\in\{y_{i-1}\}.\eta\) belongs to \(y_{i-1}\), there may be other nodes \(x_{i}\in\{y_{i-1}\}.\eta\) such that \(x_{i}\
ot\in\{y_{i-1}\}.\beta\).  
Lemma 2: _Let \(\langle y_{0},\ldots,y_{k}\rangle\in\{y_{0}\}.\beta\) and let \(\{y_{k},z\}\in L\) where \(z\
ot\in\{y_{0}\}.\beta\). Then, for all \(y_{i},0\leq i\leq k\), \(\{y_{i},z\}\in L\)._  
Proof: By the reduction process \(\omega\), when \(y_{i}\) is subsumed by \(y_{i-1}\), \(\{y_{i}\}.\eta\subseteq\{y_{i-1}\}.\eta\). Thus, if \(\{y_{i},z\}\in L\), then \(z\in\{y_{i-1}\}.\eta\) or \(\{y_{i-1},z\}\in L\).  
Lemma 3: _Let \(x\in\{x_{0}\}.\beta,z\in\{z_{0}\}.\beta\) where \(x_{0},z_{0}\in\mathcal{I}\). If \(\{x,z\}\in L\), then there exists \(y\in\mathcal{I}\) such that \(\{x,y\},\{y,z\}\in L\)._  
Proof: By Lemma 2, we know \(\exists\{x,z_{0}\},\{z,x_{0}\}\in L\). If \(\{x_{0},y_{0}\}\in L\), we are done. Thus, let us suppose not. By Proposition 4, we can assume \(\exists y\in\mathcal{I}\) (or a sequence \(y_{i}\)) such that \(\{x_{0},y\},\{y,z_{0}\}\in L\). We claim \(\{x,y\}\in L\), since otherwise \(\langle y,x_{0},\ldots,x,\ldots,z_{0},y\rangle\) is a chordless cycle of length \(\geq 4\), and hence by Proposition 3 is irreducible. Similarly, \(\{y,z_{0}\}\in L\).  
Two \(\beta\)-sets, \(\{x_{0}\}.\beta,\{y_{0}\}.\beta\) are said to be \(\beta\)**-connected** if there exists \(x,y\
eq x_{0},y_{0}\) where \(x\in\{x_{0}\}.\beta\), \(y\in\{y_{0}\}.\beta\) and \(\{x,y\}\in L\). The preceding lemmas describe links that must exist if \(\beta\)-sets are connected. These are illustrated in Figure 6.  
In this figure, solid lines denote links that are \"known\" to exist for one reason or another. The dotted (...) lines that enclose \(\beta\)-sets were established by the reduction process. Each conforms to Lemma 1. Observe that the entire set of nodes, \(\{x_{1},x_{2},z_{1},z_{2},z_{3}\}\) could constitute either \(\{x_{0}\}.\beta\) or \(\{z_{0}\}.\beta\) depending solely on the order of node reduction. This is illustrated in \(\mathcal{N}_{1}\), Figure 1, where \(\{33\}.\beta\) could have been \(\{34\}.\beta\). Proposition 2 establishes that the structure of the interior, \(\mathcal{I}\), is independent of the order in which nodes are encountered in the \(\omega\) process; however, the structure of \(\beta\)-sets produced by the code reduce can be very dependent on this order.  
The dashed links ( - - ) denote links that can be inferred from Lemma 2. For instance, \(z_{1}\) cannot subsume \(z_{2}\) unless \(x_{1}\in\{z_{1}\}.\eta\) because \(x_{1}\in\{z_{2}\}.\eta\). The (  
Proof.: We may assume that \(\rho(x,z)\cup\mathcal{I}=\emptyset\), else there is nothing to prove. Thus, we may also assume that \(\rho(x,z)\) lies entirely within connected \(\beta\)-sets. By Lemma 3, \(\exists y\in\mathcal{I}\) such that \(\{x,y\},\{y,z\}\in L\), so \(|\rho^{\prime}(x,y,z)|=2\leq|\rho(x,z)|\).