Show that that there exists a digraph $D$ such that both $od(v)$ and $id(v) $ are at least $\frac{n-1}{2}$ but $D$ is not Hamiltonian.

Question

Show that for infinitely many positive integers $n$ that there exists a digraph $D$ of oreder $n$ such that $od(v)≥ \frac{n-1}{2}$ and $id(v)≥ \frac{n-1}{2}$ for every vertex $v$ of $D$ but $D$ is not Hamiltonian.

This is what the book tells me

Let $D_1$ and $D_2$ be the copies of the digraph $K_k$ obtained by replacing each edge $uv$ of $K_k$ by the symmetric pair $(u,v)$ and $(v,u)$ of arcs. Let $D$ be obtained by identifying a vertex of $D_1$ and a vertex of $D_2$

I don't understand what the book means.

Answer 1

Some observations:

• In a hamiltonian graph each pair of vertices is connected by at least two vertex-disjoint (up to the end-points) paths; hence, if there is only one such path, then the graph can't be hamiltonian.
• One way to ensure there are no such two paths between some pair of vertices is to divide the graph into two parts, say $D_1$ and $D_2$, which share a single vertex $w$ -- any path from $D_1$ to $D_2$ (or back) has to go throug $w$, so there can be only one such path.
• Inside the parts you can do anything, and to get the highest degree possible you can take the directed version of a complete graph.
• If each part is a complete graph with $k$ vertices, then $n=2k-1$ (we share one vertex), while the degrees are $\geq k-1 = \frac{2k-2}{2} = \frac{n-1}{2}$ (inequality, because the degree of $w$ is $n-1$).

I hope this helps $\ddot\smile$

Answer 2

"Identify" means "merge" in this context, if that's what's tripping you up.