CODEWITHSUNDEEP
algorithmgraphdirected-graph
Erik Yu
Erik Yu

Reputation: 1

Relationship between vertices and edges in directed graph

Why a complete, directed graph G on n vertices and m edges has m = n(n-1) edges. But I tried lots of examples showing this statement is false, which would be n(n-1)/2 But our professor gives true to this statement. Can someone explain to me the correctness of this statement?

Upvotes: 0

Views: 4150

Answers (2)

Ashutosh
Ashutosh

Reputation: 529

I think you haven't completely understood the difference between directed and undirected graphs.

Remember in an undirected graph, the orientation of the edges doesn't matter. But in directed graphs, the orientation of edges matter.

As an analogy, suppose the two cities, A and B are represented by two nodes of a graph, and the path joining them represents the edge. Now if the edge is un-directed, you can go from A to B or vice versa. However if it's directed, it means that it's a one way road, you can only go from A to B or vice versa (depending on the orientation).

Now to answer your question, in an undirected graph, the total number of edges would be

C(n,2) = (n*(n-1))/2.

But in a directed graph of n nodes, every edge can be doubled up. i.e, One from A to B and other from B to A.

Hence, the total number of edges = 2*C(n,2)

Which translates to n*(n-1).

Upvotes: 5

Damien Prot
Damien Prot

Reputation: 593

You are talking about directed graph, so between two nodes A and B, you can have one directed edge from A to B and one from B to A.

Knowing that, you can find the expected result by induction.

Upvotes: 0

Related Questions