### Scribe and bonus submissions

Let for any two undirected graphs \( G \) and \( H \), the lexicographic graph product \( G \times H \) be a graph such that

- The vertex set of \( G \times H \) is the cartesian product \( V(G) \times V(H) \);

- Any two vertices \( (u,v) \) and \( (x,y) \) are adjacent in \( G \times H \) if and only if either \( u \) is adjacent with \( x \) in \( G \) or \( u=x \)and \( v \) is adjacent with \( y \) in \(H\).

From Lecture 1, generalize the tight example given on page 6 to an \( n \times n \) \(\{0, 1\}\)-matrix which forbids \( \left(\begin{array} 11 & 1 \\ 1 & 1 \end{array}\right) \) patterns and contains \(\Omega( n\sqrt{n}) \) many ones.

Show a polynomial time algorithm to find a shortest cycle in any graph \( G \). Prove formally its correctness and running time.

Show that for any graph \( G=(V, E) \), there exists a nice tree decomposition \( \mathcal{T} = (T, \{B_i\}_i) \) of width \( tw(G) \) such that \( |V(T)| =O(tw(G).|V|)\).

Show that for any graph \( G=(V, E) \) and a family of subsets of vertices \( \mathcal{V} = \{V_1, V_2, \dots V_q\} \) such that

- \( \cup_i V_i = V(G) \)
- For each edge \( uv \in E(G) \), \( u, v \in V_i \) for some \( i \in [q] \)
- For each \( V_i \) ( \( i\geq 2 \) ), there exists a \( j<i \), such that \( (\cup_{k=1}^{i-1}V_k) \cap V_i \subseteq V_j \)

Show formally how to create a valid tree decomposition of \( G \) using such a family \( \mathcal{V} \) as the set of bags?

Given a graph \( G= (V, E) \), let \( \beta(G) \) be the maximum number of edge-disjoint triangles in \( G \) ang \( \tau(G) \) be the minimum number of edges such that there exists a subset of edges \( F \subseteq E \) of size \( \tau(G) \), such that \( G - F\) is triangle-free.

- (100 B-points, Full Conjecture) Prove that for any graph \( G \), \( \tau(G) \leq 2 \beta(G) \).
- (50 B-points) Prove that for any graph \( G \), \( \tau(G) \leq (3- \epsilon) \beta(G) \), where \(\epsilon > 0\) is some fixed constant. This is already proven in a paper here. Points will be awarded only for proofs different than the paper.

- (100 B-points, Full Conjecture) Prove that for any graph \( G \), \( \tau(G) \leq 2 \beta(G) \).