4
The complete digraph of $n$ nodes, $K_n$ has $n(n-1)$ edges. Describe a digraph of $n$ nodes with $n(n-1)-\delta$ edges as a digraph "with $\delta$ edges removed".
A proof by induction
The following is an outline to prove by induction that every digraph of $n$ nodes with $n-2$ edges removed contains a Hamiltonian cycle.
The base case, when $n=2$ or ...
2
You can prove that any longest path contains the center vertices of the tree. It will then follow that all longest paths intersect not only at some vertex, but at the center.
2
Your explanation is correct.
And, you can not do better than $f(a) = 2a$. For example, take a complete graph on $4$ vertices: $a,b,c,d$. The Arboricity is $2$ since $(a,b), (b,c),$ and $(c,d)$ forms the first tree, and the remaining edges form the second tree. The graph is colorable with exactly four colors.
In fact, the Arboricity of a complete graph on $n$ ...
2
There is a theorem that can be used to characterize the optimal solution, which then makes algorithm design trivial. In particular, you can solve the problem in logarithmic time.
Theorem
Suppose we are hoping for a solution that uses $k$ time steps. Let $v_0$ denote the starting velocity vector, $s$ the starting position, and $t$ the target position. Let $...
1
The MST can be unique even if edge weights repeat. For example, consider the graph on $\{1,\ldots,n\}$ in which the weight of $(1,2),(2,3),\ldots,(n-1,n)$ is $1$ and the weight of all other edges is $2$.
Only top voted, non community-wiki answers of a minimum length are eligible
