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?
$\begingroup$
$\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
Add a comment
|
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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
