In-degree and out-degree of two distinct vertices in a directed graph

970 Views Asked by At

I need to prove or give a counterexample that for all $n\ge2$ there exists a directed graph of order $n$ such that every pair of distinct vertices have different out-degrees and same in-degrees.

1

There are 1 best solutions below

0
On

I would prove this by induction. So set your vertices up in a linear fashion. The one endpoint vertex has all outgoing arcs to other vertices, and then self-loops to account for the in-degree. The other end-point vertex has no outgoing arcs. The vertices in the middle each have an appropriate number of self-loops as well as arcs to the each of the next vertices in line.

Note: This assumes that you a directed multigraph is permissible here.