Since I have failed to prove the following I think it's mostly false.
Let $G$ be a directed and finite graph such that its underlying graph is a Clique.
Then, $G$ has a root.
Can someone give a contrary example?
Note:
Finite Graph means that the number of the graph's vertices and edges is finite.
$v$ is called a root of the graph if there is a path from $v$ to every node in the graph.
Best Answer
Actually, I think the statement is true. We will proceed by induction over the number of vertices $n$.
Base Case $n = 1$: Clearly the unique vertex in any graph with one node is a root.
Step Case $n \rightarrow n + 1$: Assume as induction hypothesis (IH) that the statement holds for all graphs with $n$ vertices. Now let $G$ be an arbitrary directed graph on $n + 1$ vertices such that the underlying graph of $G$ is a clique. Let $v$ be an arbitrary vertex in $G$ and consider the graph $G' = G - v$ we get by deleting $v$: It is a directed graph on $n$ vertices whose underlying graph is a clique. Hence by IH we know that there exists a root $u$ in $G'$. Now consider the edges incident to $v$ in $G$. If there exists an incoming edge to $v$ in $G$ then $u$ is also a root in $G$. On the other hand, if there does not exist an incoming edge to $v$ in $G$ then $v$ is a root in $G$ because it has an outgoing edge to all other nodes in the graph. Thus there always exists a root in $G$.