## 5 Lemmas and Proofs  
Lemma 9: _Let \(G\) be a triangle-free graph and \(B\in\mathcal{B}\) be an \(m\)-\(m^{\prime}\)-bunch. If there exists a vertex \(v\in B^{IN}\) adjacent to \(m\) such that \(\deg(v)\geq 4\) then there exists a vertex \(u\in B^{IN}\) such that \(\deg(u)=2\) within the same bunch \(B\) and \(u\) is adjacent to \(m^{\prime}\)._Proof. : Consider an \(m\)-\(m^{\prime}\)-bunch \(B\) and a vertex \(v\in B^{IN}\) such that \(\deg(v)\geq 4\). Since \(v\in B^{IN}\), we know that \(v\
ot\in M\) and, thus, it is adjacent to either \(m\) or \(m^{\prime}\). Without loss of generality, we can assume that \(v\) is connected to \(m\). Since \(\deg(v)\geq 4\), there exist three different vertices \(w_{1},w_{2},w_{3}\in N[v]\) in addition to \(m\). First, note that \(w_{1},w_{2},w_{3}\) cannot be connected to \(m\) (as they would form a triangle with \(v\)). Also note that \(w_{1},w_{2},w_{3}\
eq m^{\prime}\) due to the absence of triangles in graph \(G\). Therefore, \(w_{1},w_{2},w_{3}\) must be connected to \(m^{\prime}\). Since \(v\in B^{IN}\), all neighbors of vertex \(v\) belong to bunch \(B\). Let us number vertices \(w_{1},w_{2},w_{3}\) so that \(w_{2}\) is \"between\" \(w_{1}\) and \(w_{3}\) in the sense of the bunch structure. Then, it is easy to see that vertex \(w_{2}\) is a neighbor of \(v\) and \(m^{\prime}\) but cannot be connected to either \(w_{1}\) or \(w_{3}\) (as it would form a triangle). Therefore, \(w_{2}\) must have degree 2, which completes the proof. Figure 5 illustrates the existence of a vertex of degree 2 in a bunch when there is a vertex of degree of at least 4. The left side shows a vertex \(v_{1}\) with a degree of at least 4 adjacent to \(m\), while the right side demonstrates how this implies the existence of a vertex \(z\) with a degree of exactly 2 adjacent to \(m^{\prime}\):  
Lemma 10.: _Let \(B\) be an \(m\)-\(m^{\prime}\)-bunch where the endpoint \(m\) has a degree at least 3 (\(\deg(m)\geq 4\)). If \(m\) selects a vertex \(v\in B^{IN}\) as \(\beta(m)\) then \(m^{\prime}\) will be added to the set \(D_{1}\) in phase 1 of the algorithm._  
Proof. : Let us assume by contradiction that the lemma's assumptions are satisfied, but \(m^{\prime}\
ot\in D_{1}\). From our assumption, we know that \(m\) has a degree of at least 4 (\(\deg(m)\geq 4\)). Furthermore, from Lemma 9, we know that in bunch \(B\) there exists a vertex \(u\in B^{IN}\) such that \(\deg(u)=2\) and \(u\) is adjacent to \(m^{\prime}\). Moreover, \(u\) is adjacent to a vertex \(v\) such that \(m(v)=m\). According to the definition of phase 1 of the algorithm, vertex \(u\) with degree 2 selects vertex \(\beta(u)\) with the smallest ID among vertices with the highest degree in its closed neighborhood \(N[u]\). Since from our contradiction assumption we know that \(m^{\prime}\
ot\in D_{1}\), vertex \(u\) cannot select vertex \(m^{\prime}\) as \(\beta(u)\), and, thus, \(m^{\prime}\) will not be added to \(D_{1}\). Otherwise, \(m\) would be dominated and would not select any vertex as \(\beta(m)\) in phase 2 of the algorithm. We obtain a contradiction with the lemma's assumption, which completes the proof. Figure 5. Example of a bunch structure with a vertex of degree 4, which implies the existence of a vertex of degree 2. **Lemma 11**. : _Let \(v\in V\setminus N[D_{1}]\) be a vertex that is not dominated in the first phase of the algorithm, and let \(\gamma(v)\) be the vertex chosen by \(v\) in step 12 of the algorithm instead of vertex \(\beta(v)\). Then, \(\beta(v)\
otin D_{1}\cup D_{2}\)._  
Proof. : Let us assume, by contradiction, that \(\beta(v)\in D_{1}\cup D_{2}\) and vertex \(v\) chose \(\gamma(v)\) instead of \(\beta(v)\) in phase 2 of the algorithm. First, note that \(\beta(v)\) cannot belong to \(D_{1}\), because vertex \(v\) adjacent to \(\beta(v)\) would not be considered in the second phase of the algorithm. Therefore, from our contradiction assumption that \(\beta(v)\in D_{1}\cup D_{2}\) and the fact that \(\beta(v)\
otin D_{1}\) we conclude that \(\beta(v)\in D_{2}\).