Given a 3-uniform hypergraph $H=(V, E),$ the matching number $\nu(H)$ is the maximum number of pairwise-disjoint edges in $E(H) .$ The cover number $\tau(H)$ is the size of the smallest set of vertices $A \subseteq V(H)$ such that for every edge $e \in E(H)$ we have $e \cap A \neq \emptyset .$ Prove that for all 3-uniform hypergraphs $H, \tau(H) \leq 3 \nu(H)$.
From the description the two numbers sound like the same thing to me? i.e. we can select a vertex from each edge in the maximal set of pairwise-disjoint edges to obtain $\tau(H)$ (so we actually have $\tau(H) \leq \nu(H)$). Am I missing something here?
Best Answer
It is possible that taking one vertex from each of the edges of a matching does not form a vertex cover.
Consider the following example:
This has $\tau = 2$ and $\nu = 1$, since all edges pairwise intersect, but there is no single vertex that is contained in each edge.