Can someone prove (or disprove) the following? If a weakly connected simple oriented graph, oriented meaning a directed graph where no arcs are bidirected, has every vertex have the same indegree as outdegree then the graph is strongly connected. If that is the case can we generalize to directed rather than oriented? If that is not the case, I would like a counterexample, and would making each vertex have the same in/outdegree as every other vertex as a more strict condition make it work?
[Math] Same Indegree as Outdegree
graph theory
Related Solutions
Let's orient a $K_5$ to have arcs 12, 23, 34, 45, 51 (which I think is enough to make it strongly connected), 13, 14, 24, 25, 35. Each vertex has total degree $4$, which is even, but vertex $1$ has indegree $1$ and outdegree $3$.
It is easy to see that having indegree, outdegree $\ge 1$ for every vertex is a necessary condition for a graph to be strongly connected. Otherwise, you would have an unreachable vertex or a vertex from which there are no paths.
But it is not a sufficient condition; counterexample below.
Draw two directed triangle graphs and join them by a single directed edge.
Since the degrees are not balanced, there is a directed path from one strongly connected component to the other, but not the other way around; despite the underlying undirected graph being connected.
Best Answer
Lemma: If $G$ is a directed graph where each vertex has indegree equal to outdegree, and $A$ is a subset of the vertices of $G$, then the number of edges going from a vertex in $A$ to a vertex not in $A$ is the same as the number of edges going from a vertex not in $A$ to a vertex in $A$ (i.e. $A$ also has "indegree" equal to "outdegree").
Now take an arbitrary vertex $v\in G$ and consider the set $V$ of vertices you can reach from $v$. Assume this isn't the entire graph, and use that $G$ is weakly connected along with the above lemma to reach a contradiction.