D. Transitivity
Given a simple undirected graph with $n$ vertices and $m$ edges, and it’s guaranteed that
We define an undirected graph to be transitive if and only if for any two different vertices $u, v$ :
If there exists a path starting from $u$ and ending at $v$ in the graph, then there should exists an edge connected $u$ and $v$ in the graph.
Now you should add some undirected edges to the graph (add at least one edge). You need to ensure that after adding edges, the graph is still a simple undirected graph and is transitive.
The question is, how many edges need to be added at least?
Recall that a simple undirected graph is an undirected graph that does not have more than one edge between any two vertices and no edge starts and ends at the same vertex.
$n_{k}^9$