Prove or disprove the following conjecture For all directed

Prove or disprove the following conjecture: For all directed graphs without loops (i.e. where every edge is incident to two separate vertices), the sum of the out-degrees of the vertices must equal the sum of the in-degrees of the vertices.

Solution

For all directed graphs without loops,

A.-------------->-----. B

A vertex is apoint that can be drawn to connect by edge to another vertex. i.e A,B are two vertices

An edge is defined as line drawn between two edges. i.e AB is an edge.

directed graph has all edges directed (arrow symbol) to connect two vertices for non loop graphs.

i.e AB is directed edge.

degree(d): The number of edges incident on vertex is called degree.

indegree(d_i): number of edges towards iincident on vertex is called indegree.

outdegree(d_o): number of edges outwards incident from the vertex is called outdegree.

Let G = (V;E) be a digraph. Then number of edges = |E| = 2 d_i =2 d_o

_=> 2 d_i    =2 d_o

=> d_i    = d_o

Proof:

-> For any digraph without loops , Each edge is drawn between two vertices.

as A.-------------->-----. B

=> then indegree of vertex A = 0

and

=> outdegree of vertex A = 1

similarily

=> indegree of vertex B = 1

and

=> outdegree of vertex B = 0

Sum of indegree of vertices = indegree of vertex A + indegree of vertex B = 0 + 1 =1 = d_i

Sum of outdegree of vertices = outdegree of vertex A + outdegree of vertex B = 1 + 0 =1 = d_o

Because of each indegree of vertex is out degree of another vertex.

Therefore d_i    = d_o for every digraph without looops.