If the graph is undirected, then n-1, if directed then n(n-1)/2.

Of course it's n * (n-1) / 2 , like "ha" mentioned too. It's 1 + 2 + ... + (n-1). Which is n * (n-1) / 2. If you really want to prove it, by induction it's most clear. But you should visualize it, without needing a specific example. Just think that an edge has at most n-1 connections, with all the other edges; then, if you eliminate this edge from the graph, and do the same reasoning for the rest of n-1 nodes, you will get the above sum.

Sorry, I didn't see it was with no cycles :), just observed it now :), my mistake - and cannot delete the previous post.

it's n-1. In response to ha, your 3 nodes and 4 nodes examples both have cycles.

n * (n - 1) / 2 For example, 2 nodes: 1 edge, (0,1) 3 nodes: 3 edges, (0,1), (0,2), (1, 2) 4 nodes: 6 edges, (0,1), (0,2), (0, 3), (1, 2), (1, 3), (2, 3)