How do I prove that a DAG with the maximum of edges + one edge must have a cycle?

Question

Question: How do I prove that a DAG with A($n$) edges + one edge must have a cycle?

$\begin{equation} \text{A}(n)=\frac{n\cdot(n-1)}{2} \end{equation}$

My answer: What happens if we add another edge to a DAG with A($n$) edges. Well, the only nodes that we can still add edges to are just previous nodes, which means that we will get a cycle if we add an edge.

The thing I need help with is to enforce my answer with the pigonhole-principle, but I dont know how.

Answer 1

Here's an idea/ hint: Show that a digraph of order $n$ with $A(n) + 1$ edges must have a $2$-cycle.

Click below for a proof outline:

There are $A(n) = \binom{n}{2} = \frac{n(n-1)}{2}$ pairs of vertices in the digraph, but $A(n)+1$ edges. So by the pigeonhole principle, at least one pair of vertices, say $u$ and $v$, has both directed edges $uv$ and $vu$ between it. Which means the digraph has a $2$-cycle.