0
$\begingroup$

Consider a directed graph G in which there is exactly one edge between any two distinct vertices in G. Prove that there is a vertex in G that is in the distance-2 neighborhood of every other vertex in G. Assume that there are at least two vertices in G.

$\endgroup$
0
$\begingroup$

Proof by induction on $n$ the number of vertices: for $n = 2$ it is obvious. If the statement is true for $n = k$, we show it is true for $n = k+1$. In a graph with $n = k+1$ remove one of the vertices, say $v_{k+1}$, that has the maximum outdegree. Now in the remaining graph, there is a vertex $v^*$ that is in the distance-2 neighbourhood of every vertex in $\{v_1, v_2, \dots, v_k\} - \{v^*\}$. Now, again consider $v_{k+1}$, if $v_{k+1}u$ is an edge in this graph for any $u$ that has $v^*$ in distance-1 neighbourhood, then $v^*$ is in the distance-2 neighbourhood of every vertex including $v_{k+1}$. Otherwise, the outdegree of $v_{k+1}$ is smaller than $k -$ (#of vertices that have $v^*$ in distance-1 neighbourhood). Note that the outdegree of $v^*$ in this case is $k+1 -$ (#of vertices that has $v^*$ in distance-1 neighbourhood) which contradicts the fact that $v_{k+1}$ has maximum oudegree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.