## 2 Bunch Decomposition Technique for Planar Graphs
For vertex \(v_{3}\) to belong to set \(T\) that is incident to face \(f\), we must add edge \(\{v_{1},v_{3}\}\) (also marked in Figure 3 with a dashed line). However, it is not possible for three vertices incident to a face of degree 3 to belong to \(T\). Otherwise, there would have to be three vertices from \(V\setminus M\) lying on this face and they would have to be connected to each other. This is impossible in a triangle-free graph. This example is shown in Figure 3. The potential edge between vertices \(v_{3}\) and \(v_{5}\) is marked in red with a bold dashed line. However, such an edge cannot exist in a triangle-free graph, as it would form a triangle with the existing edges (specifically with edges \(\{v_{1},v_{3}\}\) and \(\{v_{1},v_{5}\}\)). Consequently, vertex \(v_{5}\) lies only on one bunch (between \(m_{3}\) and \(m_{1}\)), and it does not belong to the bunch between \(m_{2}\) and \(m_{3}\), because the path \((m_{2},v_{3},v_{5},v_{6},m_{1})\) would have five vertices, which exceeds the maximum path length in a bunch, which is four vertices. From the analysis of possible connections of the vertices in a face of degree 3 in a triangle-free graph, it follows that we can have at most two vertices belonging to \(T\) that are incident to face \(f\). In the presented example, these are vertices \(v_{1}\) and \(v_{3}\). Therefore, the maximum number of vertices belonging to \(T\) that are incident to a face \(f\) of degree 3 is two. **Lemma 7**: _For each face \(f\) of degree \(d_{H}(f)\geq 4\) in the bunch graph \(H\) of a triangle-free graph \(G\), the number of vertices belonging to the set \(T\) that are incident to this face \(f\) does not exceed the degree of the face, i.e., \(d_{H}(f)\)._  
Figure 3: Vertices from set M forming a triangle (face of degree 3) in the bunch graph H, with pairs of vertices added on each path between vertices from set M. Proof. : Let us consider a face \(f\) of degree \(k=d_{H}(f)\geq 4\) in the bunch graph \(H\). This face is bounded by \(d_{H}(f)\) vertices belonging to the set \(M\). Each edge in graph \(H\) corresponds to a bunch in graph \(G\), so we have \(d_{H}(f)\) bunches associated with face \(f\). Figure 4 shows an example of a face of degree 4, where vertices \(m_{1}\), \(m_{2}\), \(m_{3}\), and \(m_{4}\) form a square, and between each pair of vertices from set \(M\) there are at most two vertices from \(V\setminus M\):  
Note that an edge such as \(\{v_{1},v_{5}\}\) cannot exist in Figure 4, because it would cause the considered face \(f\) to have a degree less than the fixed value \(k\) in graph \(H\). Again, to obtain the maximum number of vertices belonging to \(T\) that are incident to face \(f\), we must add dashed edges between \"opposite\" vertices, as shown in Figure 4. However, there is an important difference compared to the case of a face of degree 3. In the case of a face of degree 3, we have only two vertices belonging to \(T\) that are incident to face \(f\), while in the case of a face of degree \(k\) we have \(k\) vertices belonging to \(T\) that are incident to face \(f\). Closing the \"cycle\" does not create a triangle in graph \(G\) in this case. Therefore, the maximum number of vertices belonging to \(T\) that are incident to a face of degree \(d_{H}(f)\geq 4\) is \(d_{H}(f)\). For triangle-free graphs, \(|T|\leq 4|M|\). Proof. : We want to count the maximum number of possible vertices \(T\) in relation to the number of bunches, which is \(|E_{H}|\). Let us consider the bunch graph \(H=(M,E_{H})\). From Lemma 6, we know that for each face \(f\) in graph \(H\) with degree \(d_{H}(f)=3\), there are at most two vertices belonging to \(T\). Moreover, from Lemma 7, we know that for each face \(f\) in graph \(H\) with degree \(d_{H}(f)\geq 4\) there are at most \(d_{H}(f)\) vertices \(v\in T\). Let us note that each face with degree \(d_{H}(f)\geq 4\) uses \(d_{H}(f)+2(d_{H}(f)-3)\) edges.