I am trying to figure out the least number of directed edges that would be bi-directional after constructing a graph with $2k-1$ nodes that are each $k$ in-degree. For example, $2(2)-1=3$ nodes that are $2$ in-degrees would force the graph to have $3$ symmetric edges.
Thank you in advance!
I assume that there can be at most one directed edge from a vertex $i$ to a vertex $j$. The graph has at least $k(2k-1)$ edges. The number of unordered pairs of distinct vertices is ${2k-1\choose 2}= (k-1)(2k-1)$. Hence we need at least $k(2k-1) - (k-1)(2k-1) = 2k-1$ symmetric edges. This can be achieved by taking the vertex set to be $V=\mathbb{Z}/(2k-1)\mathbb{Z}$ (the integers modulo $2k-1$) and drawing for each $i\in V$ drawing an edge from $i-1,i-2,\dots,i-k$ to $i$.
