0
$\begingroup$

please tell me a equation to find maximum number of non loop edges that can exist in an undirected graph.

for example if vertices are 10 then how many non loop edges can exist?

$\endgroup$
3
  • $\begingroup$ Try it with some small numbers. Draw 3, 4, or 5 vertices, then add edges until you can't add any more without making a loop. Then look for a pattern. $\endgroup$ – MartianInvader Apr 13 '14 at 15:38
  • $\begingroup$ What do you mean by a "loop"? To me, a "loop" is an edge joining a vertex to itself. A graph with two vertices $u,v$ can have as many edges joining $u$ to $v$ as it wants. If you're talking about simple graphs, there can be at most one edge $uv$, but then the question of loops wouldn't even come up. $\endgroup$ – bof Dec 9 '14 at 15:41
  • $\begingroup$ possible duplicate of How can I prove the maximum number of edges? $\endgroup$ – Rebecca J. Stones Jun 28 '15 at 4:27
1
$\begingroup$

If you have a simple graph, then the extremal case is a complete graph. In which case, there is an edge between each vertex, so there are $\binom{n}{2}$ such edges at most.

$\endgroup$
0
$\begingroup$

An undirected graph is one in which edges have no orientation. The edge (a, b) is identical to the edge (b, a), i.e., they are not ordered pairs, but sets {u, v} (or 2-multisets) of vertices. The maximum number of edges in an undirected graph without a self-loop is n(n - 1)/2. So , 10 * 9 / 2 = 45

Source : http://en.wikipedia.org/wiki/Graph_(mathematics)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.