A procedure for Topological sort, proof for its correctness
b. As operation $1$ cannot be performed, $H$ must be a DAG. Consider a topological sort of $H$. As $3$ cannot be performed, if $u$ precedes $v$ in the topological sort, there is a path from $u$ to $v$. Start at the initial vertex in the sort and keep moving forward until we find a vertex which has more than one outgoing edges (if each vertex has only one outgoing, then it is a line graph). Let $u$ have edges to $v$ and $w$ and let $v$ precede $w$. Then there is path from $v$ to $w$, which gives a path from $u$ to $w$ that doesn't include $u \rightarrow w$, a contradiction as operation $2$ can be performed here.

c. As deleting edges will not alter DAG property, we only need to check $3$. A cycle is formed only when we add an edge $u \rightarrow v$, when there was a path from $v$ to $u$ already. As $3$ doesn't add such edges, DAG is maintained.

d. Let $H$ be obtained from $G$ by a single operation. We show that any topological sort of $H$ is also valid for $G$ (note that the converse need not be true). For this we need to show that if there was a path from $u$ to $v$ in $G$, then there is path from $u$ to $v$ in $H$ too. Some path can be broken only when we are removing edges. So clearly operation $3$ will not cause any problem here. Also, in $2$, we are only removing those edges $u \rightarrow v$ where there is already a path from $u$ to $v$. So for any path from $w$ to $z$, containing that edge, we can just replace that edge by the path from $u$ to $v$, maintaining a path from $w$ to $z$ in $H$. And $G$ is DAG, so $1$ never happens.

e. First observe how each of $s$, $e$ and $p$ change with each operation. With operation $1$, $s$ reduces by at least $1$, $e$ reduces by $1$ and $p$ can decrease by close to $n^2$ (almost all paths might be broken). With $2$, $s$ might reduce by $1$ (not necessary though), $e$ reduces by $1$ and $p$ is unchanged. With $3$, $s$ doesn't change, $e$ increases by $1$ and $p$ increases by at least $1$. Notice that as we are going towards line graph, we are trying to reduce number of edges ($e$), remove cycles ($s$) while increasing $p$. So in $as+bp+de+c$, we expect $a$ and $d$ to be positive and $b$ to be negative. The worst case changes in $s,e,p$ for each operation are

$$
\begin{array}{cccc}
 &amp; s &amp; e &amp; p \\
1. &amp; -1 &amp; -1 &amp; -n^2 \\
2. &amp; 0 &amp; -1 &amp; 0 \\
3. &amp; 0 &amp; 1 &amp; 1
\end{array}
$$

As $s$ never increases, we can make $a$ as large as we want. As we can scale $a,b,d$ by a constant, lets keep $d=1$. With these observations we can get one possible set of values for $a,b,d$ as $2n^2$, $-2$ and $1$ respectively. And pick $c$ as negative of the value at line graph.