Proving m ≤ α(G)τ in a graph

Question

I was given the following exercise:

Let $G$ be a graph of $m$ edges without simple cycles of length 3. Let $α(G)$ be the number of vertex in a maximum independent set of $G$ and let $τ$ be the number of vertex in any vertex cover of $G$. Prove that $m≤α(G)τ$.

However, I'm stuck trying to find the relationship. I know some properties, but I can't seem to find one that would make sense to use the lack of simple cycles of length 3.

Answer 1

I finally figured out the solution. Suppose we have a minimum vertex cover $τ_{min}$, so that $|E|= \sum_{i=1}^{τ_{min}} E_{V_i} \leq \sum_{i=1}^{τ_{min}} N(V_i) $

where $E_{V_i}$ is the number of edges incident o $V_i$ in the vertex cover. However, the neighbors of $V_i$ form an independent set, because if there where an edge between two of them, there would be a cycle of length 3. Then:

$|E| \leq \sum_{i=1}^{τ_{min}} N(V_i) \leq \sum_{i=1}^{τ_{min}} α(G) = τ_{min} α(G) \leq τ α(G) $

Answer 2

This follows from the following two facts:

1. If $U$ is a vertex cover, then $m \le \sum_{u \in U} \deg(u)$. (The right-hand side counts each edge at least once.)
2. If $G$ is triangle-free, then $\deg(v) \le \alpha(G)$ for all vertices $v$. (The neighborhood of any vertex is an independent set.)

The second fact in particular should be something that immediately comes to mind when you think about triangle-free graphs.