For each $n \ge 1$ answer true or false: Every simple directed graph on $n$ vertices contains $2$ vertices with the same indegree or $2$ vertices with the same outdegree. Explain your answer in every case.
Currently stuck on this..was hoping if someone could walk me through this
Note: For each $n \ge 1$ answer true or false (explain why)
For $n=1$ this is simply false. For $n=2$ we can show this is false as well, as $v_1$ to $v_2$ will have only one direction. For $n=3$ we can construct a triangle where this also false. I'm trying to induct on the number of vertices but not sure how to show past what happens when adding a vertex. I suspect it's false for all $n$ greater than or equal to one.
Let's try to find a counterexample for $n=4$.
If the digraph is simple, the possible outdegrees are $0,1,2,3$. If they are all different, we must have one of each. Call the vertices $v_0,v_1,v_2,v_3$ where $\operatorname{od}(v_i)=i$.
The number of edges is the sum of the outdegrees, $0+1+2+3=6$. Since $6=\binom42$, every pair of vertices is joined by an edge; that is, we have an oriented complete graph aka a tournament. Therefore we have $\text{ outdegree }+\text{ indegree }=3$ at each vertex; that is, $v_0$ has outdegree $0$ and indegree $3$, $v_1$ has outdegree $1$ and indegree $2$, etc. And now the digraph is completely determined: we have an edge from $v_i$ to $v_j$ if $j\lt i$.
Q.E.D.!