Skip to main content
1 of 2
domotorp
  • 19k
  • 3
  • 58
  • 127

Yes, it is true. For every vertex $v$ of the hypergraph $\pi$, consider the edges of the graph $G$ that run between hyperedges that intersect in $v$. This will be a clique, which we can denote by $K_v$. We can select any vertex of the clique for each $v$, this gives a vertex cover of size at most "$\ell$".

The linearity seems not needed. It would imply, btw, that any two such cliques are edge-disjoint, that is, $K_v\cap K_u\cap E=\emptyset$. Therefore in this case the edgeset of the graph, $E$, is an edge-disjoint union of cliques.

domotorp
  • 19k
  • 3
  • 58
  • 127