Intereting Posts

Rewriting of functional equation $f(xy)=f(x)+f(y)$
Why is $5^{n+1}+2\cdot 3^n+1$ a multiple of $8$ for every natural number $n$?
Integration of exponential with square
Finite automaton that recognizes the empty language $\emptyset$
Number of Subspaces that contains other Space
Metric is continuous, on the right track?
Meaning of closed points of a scheme
Minimal polynomials and cyclic subspaces
What are Different Approaches to Introduce the Elementary Functions?
An Infinite Double Summation $\sum_{k=1}^{\infty} \sum_{n=1}^{\infty} \frac{1}{n^2k^2(n+k)^2}$?
Find all primes $p$ such that $\dfrac{(2^{p-1}-1)}{p}$ is a perfect square
Is it misleading to think of rank-2 tensors as matrices?
Is $H^2\cap H_0^1$ equipped with the norm $\|f'\|_{L^2}$ complete?
Optimal control
Calculus conjecture

I’m studying graphs in algorithm and complexity,

(but I’m not very good at math) as in title:

Why a complete graph has $\frac{n(n-1)}{2}$ edges?

And how this is related with combinatorics?

- Combining kindergardeners in 'fair' cookie-baking groups. Kirkman's schoolgirl problem extended version
- Challenging identity regarding Bell polynomials
- If I randomly generate a string of length N from an alphabet {A, B, C}, what's the likelihood that exactly k characters will be the same?
- In how many ways 3 numbers can be chosen from a from the set {1, …, 18} so that their sum is divisible by 3?
- Combinatorics Pigeonhole problem
- How to solve second degree recurrence relation?

- Relations of a~b iff b = ak^2
- Demonstrate that if $f$ is surjective then $X = f(f^{-1}(X))$
- A game with two dice
- Combinatorial interpretation of a sum identity: $\sum_{k=1}^n(k-1)(n-k)=\binom{n}{3}$
- Prove that any set of 2015 numbers has a subset who's sum is divisible by 2015
- Number of Unique Sequences with Circular Shifts
- Prove that if m and n are positive integers, and x is a real number, then: ceiling((ceiling(x)+n)/m) = ceiling((x+n)/m)
- What are the total number of ordered permutations of a list of elements (possibly repeated)?
- Arranging books on the shelf.
- Flipping heads 10 times in a row

A simpler answer without binomials: A complete graph means that every vertex is connected with every other vertex. If you take one vertex of your graph, you therefore have $n-1$ outgoing edges from that particular vertex.

Now, you have $n$ vertices in total, so you might be tempted to say that there are $n(n-1)$ edges in total, $n-1$ for every vertex in your graph. But this method counts every edge twice, because every edge going out from one vertex is an edge going into another vertex. Hence, you have to divide your result by 2. This leaves you with $n(n-1)/2$.

A complete graph has an edge between any two vertices. You can get an edge by picking any two vertices.

So if there are $n$ vertices, there are $n$ choose $2$ = ${n \choose 2} = n(n-1)/2$ edges.

Does that help?

$\frac{n(n-1)}{2}$ comes from simple counting argument. You could directly say that every edge is obtained by choosing a pair of vertices so the number is $C(n,2) = \frac{n(n-1)}{2}$ or you could take the other way of counting. Label the vertices $1,2, \ldots ,n$. The first vertex is now joined to $n-1$ other vertices. The second vertex has already been joined to vertex $1$ and hence has to be joined to the remaining $n-2$ vertices and in general the $k^{th}$ vertex has already been joined to the previous $k-1$ vertices and hence has to be joined to the remaining $n-k$ vertices. So the total number of edges is given by $(n-1) + (n-2) + \ldots 2 + 1 = \frac{n(n-1)}{2}$.

$\frac{n(n-1)}{2} = \binom{n}{2}$ is the number of ways to choose 2 unordered items from n distinct items.

In your case, you actually want to count how many unordered pair of vertices you have, since every such pair can be exactly one edge (in a simple complete graph).

suppose $(v,u)$ is an edge, then v can be any of the vertices in the graph – you have n options for this. u can be any vertex that is not v, so you have (n-1) options for this. the problem is that you counted each edge twice – one time as $(u,v)$ and one time as $(v,u)$ so you need to divide by two, and then you get that you have $\frac {n(n-1)}{2}$ edges in a complete simple graph.

- Order of an element in a finite cyclic group
- How to efficiently solve a series of similar matrix equations using the LU decomposition
- Is Kaplansky's theorem for hereditary rings a characterization?
- What does a standalone $dx$ mean?
- $\# \{\text{primes}\ 4n+3 \le x\}$ in terms of $\text{Li}(x)$ and roots of Dirichlet $L$-functions
- What is rotation when we have a different distance metric?
- Proof of Hartogs's theorem
- Proving inequality $\sqrt{\frac{2a}{b+c}}+\sqrt{\frac{2b}{c+a}}+\sqrt{\frac{2c}{a+b}} \leq \sqrt{3 \left(\frac{a}{b}+\frac{b}{c}+\frac{c}{a}\right)}$
- A Borel set whose projection onto the first coordinate is not a Borel set
- Why it is absolutely mistaken to cancel out differentials?
- Derived category and so on
- What is the phase shift of a sinusoidal function?
- Infinity times $i$
- Equivalence of the definitions of the Subbasis of a Topology
- Cover and extension of a Lie group