Directed Acyclic Graph Question

Question

Prove that in any directed acyclic graph (DAG) we have $2 \cdot |E| \leq |V|(|V|−1)$. Use induction on the number of vertices.

Answer 1

What happens when you have a single vertex? You have no arcs, and so $E = 0$ and $V(V-1) = 0$. When you have two vertices, you can have at most one arc. So $E = 1$, and $V(V-1) = 2$. Now assume true up to $V = K$. On the $K+1$ case, add a vertex and draw arcs from each vertex in the existing graph to the new vertex. You are adding $V$ arcs. So $2E_{k} \leq K(K-1)$ by the Inductive Hypothesis. And so $2E_{k} + 2K \leq K(K-1) + 2K = K(K+1)$.