Question

Let G be a directed graph on n vertices and maximum possible directed edges; assume that n ≥ 2.

(a) How many directed edges are in G? Present such a digraph when n = 3 assuming vertices are 1, 2, and 3. You do not have to present a diagram, if you do not want to; you can simply present the directed edges as a set of ordered pairs.

b) Is G, as specified in the problem, reflexive? Justify briefly.

c) Is G, as specified in the problem, symmetric? Justify briefly.

(d) Is G, as specified in the problem, transitive? Justify briefly.

(e) Is G as specified in the problem, antisymmertic? Justify briefly.

Answer 1

a) In case of directed graph, each vertex can connect to n-1 other vertex. So total edges = n x (n-1)

but since the edges are directive, then every edge should be counted once and hence total possible directed edge = (n x (n - 1)) / 2

For n=3, total possible edges = (3 x 2) / 2 = 3.

So, let vertices = {1,2,3} then possible edges are {(1,2),(1,3),(2,3)}. Order pair can be revesred as per the direction of the edge. But, at all possible times, there will be just 3 edges here.

b) For G to be reflexive every node should have self loop i.e a edge set of {(1,1),(2,2),(3,3)} can be considered as reflexive.

But, G fails to have self loops. As a simple gaph is not allowed for self loops.

Hence G cannot be reflexive

c) For G to be symmetric, for every every vertex (a,b) there should be (b,a).

But since our graph is directive. so edge (1,2) is not equal to edge (2,1).

Hence, G cannot be symmetric.

d) For G to be transitive, If there exist an edge (a,b) and (b,c) then there must be an edge (a,c)

In our graph G, It is possible as for the existence of edge (1,2) and (2,3) there can exist an edge (1,3) making the graph transitive.

Hence, G can be transitive