As shown in class, when n is 1 or 2, the only n-vertex triangle-free graph with the maximum number of edges is $K_{ \lfloor {\frac n 2} \rfloor, \lceil {\frac n 2} \rceil}$. Now we show that it also holds for larger n by induction.
Suppose this is true for all $n \le k-1$. As in the original proof, Let G be a simple k-vertex graph with no 3-cycles and $|E(G)|=f(k)$. For a fixed edge $x \to y$ in G, let $G’=G-x-y$. According to induction assumption, $G’=K_{ \lfloor {\frac {k-2} 2} \rfloor, \lceil {\frac {k-2} 2} \rceil}$. For x and y respectively, each of them can only connects with vertices in at most one side of complete bipartite graph, otherwise induces 3-cycle. To have $|E(G)|=f(k)$, we need $k-2$ extra edges incident to x or y, besides $x \to y$. The only way to do so is $K_{ \lfloor {\frac k 2} \rfloor, \lceil {\frac k 2} \rceil}$.
The original question is equivalent to finding minimum number of edges in a simple n-vertex connected graph G that has no independent set of order 3, which is equivalent to finding the minimum number of edges in a simple n-vertex connected graph G whose complement has no 3-cycle. This is true because a graph G has independent set of order 3 if and only if complement of G has 3-cycle.
Mantel’s thm says that the maximum number of edges in a simple n-vertex connected graph without 3-cycle is $\lfloor \frac{n^2}{4} \rfloor$. Now we claim that the maximum number of edges in a simple n-vertex graph without 3-cycle is still $\lfloor \frac{n^2}{4} \rfloor$, since disconnected graph is combination of connected components, say $\sum_i n_i = n$, yet $\sum_i \lfloor \frac{n_i^2}{4} \rfloor < \lfloor \frac{n^2}{4} \rfloor$ whenever $n>1$.
Now we claim that the maximum number of edges in a simple n-vertex graph without 3-cycle whose complement is connected is $\lfloor \frac{n^2}{4} \rfloor-1$, because the only way to achieve $\lfloor \frac{n^2}{4} \rfloor$, according to Q1, is $K_{ \lfloor {\frac k 2} \rfloor, \lceil {\frac k 2} \rceil}$. Yet the complement is not connected. On the other hand, disconnecting an edge in the biparite graph gives a valid graph with number of edges $\lfloor \frac{n^2}{4} \rfloor-1$.
Now back to original question, the minimum number of edges is ${n \choose 2} - (\lfloor \frac{n^2}{4} \rfloor-1)={n \choose 2} - \lfloor \frac{n^2}{4} \rfloor+1$.
Add 5 imaginary edges from y to x. Now according to Euler’s Theorem, $E(G)$ can be partitioned into directed cycles. Removing these 5 imaginary edges from these directed cycles leads 5 edge-disjoint paths from x to y, no matter these 5 imaginary edges are in the same directed cycles or not.
According to Landau’s thm, if every vertex has outdegree $\frac{n*(n-1)/2}{n}=\frac{n-1}{2}$, then they’re all kings. The following is a valid construction: $V(G)=\{ v_0, v_1 \dots v_{n-1} \}$. For vertex $v_i$, $N^+(v_i)= \{ v_{ (i+k) \mod n } : 1 \le k \le \frac{n-1}{2} \}, N^-(v_i)=V(G) - \{v_i\} - N^+(v_i)$.
No, such a tournament does not exist. There are totally $n*(n-1)/2=6$ edges. Then $\sum d^+(x)=\sum d^-(x)=6$. Then the unique sorted out-degree sequence should be $2,2,1,1$, otherwise some vertex cannot be reached. The following graph will be the only way. However, B cannot reach A in two steps.