Acyclic Directed Graphs and the edges

0
votes

Okay, I know that a directed acyclic graph (DAG) has E=V-1 edges. E = number of edges. V = number of vertices.

So the question is, "In a directed graph G, the number of edges is always less than the number of vertices." True or false?

Thanks for the help.

1
graph
What have you tried to solve this problem? We don't give away answers on this site; we help people who show that they've put in effort and are stuck on a specific point. - musical_coder
This question appears to be off-topic because it is about Math - madth3

1 Answers

1
votes

Assume N vertices/nodes, and let's explore building up a DAG with maximum edges. Consider any given node, say N1. The maximum # of nodes it can point to, or edges, at this early stage is N-1. Let's choose a second node N2: it can point to all nodes except itself and N1 - that's N-2 additional edges. Continue for remaining nodes, each can point to one less edge than the node before. The last node can point to 0 other nodes.

Sum of all edges: (N-1) + (N-2) + .. + 1 + 0 == (N-1)(N)/2