Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

On my book it says that the maximum number of edges E, in a simply connected undirected unweighted graph $G(V,E)$ is $\dfrac{|V|(|V|-1)}{2}$.

How can I show that it is true? Thanks!

share|cite|improve this question
    
It seems there are some unfortunate typos in the question. (1.) The answer should be $\frac{1}{2}|V|(|V|-1)$ and not what you quote. (2.) I haven't heard of the term "simply connected" in the context of a graph, at least not at such an elementary level. It should just be "simple" (or, "simple, connected" but the answer doesn't change). Which book are you following? Are you sure you didn't make any mistakes in writing the question? – Srivatsan Sep 3 '11 at 13:34
    
Related(?): math.stackexchange.com/questions/17747/…. – Srivatsan Sep 3 '11 at 13:35
    
This question answered in the link below: math.stackexchange.com/questions/1244095/… – Herman Jaramillo Sep 24 '15 at 20:46
up vote 9 down vote accepted

I will assume for a moment that you meant $\dfrac{|V|(|V| - 1)}{2}$, as it is hard to describe the number of edges by using the number of edges. And this arises naturally, as this is the number of pairs from $|V|$ vertices, i.e. this is ${|V| \choose 2}$. If we had any more, than the graph would not be simple.

Alternatively, you might now know about complete graphs, which have the maximal number of edges for a set of vertices. They have exactly this number of edges. Having any more would force it to be nonsimple, again.

share|cite|improve this answer
    
Perhaps it is just me, but the word pairing sounds like a matching to me. Won't "pair" suffice? – Srivatsan Sep 3 '11 at 13:28
    
@Srivatsan I could believe that. ;p – mixedmath Sep 3 '11 at 13:32

Another way to view this problem is to use the ``Handshaking Lemma''. Viewing the vertices as people and the edges as handshakes, we could ask how many handshakes are possible among $n$ people if every pair of people shakes hands exactly once. Every person can shake hands with the other $n-1$ people in the room. There are not, however, $n(n-1)$ handshakes, since we are counting every handshake exactly twice in this way (this counts Alice shaking Bob's hand as a different handshake than Bob shaking Alice's hand). Thus, $\frac{1}{2}n(n-1)$ gives us the correct count.

share|cite|improve this answer

Perhaps you could use induction. Every new vertex you add must have enough edges added to connect to each of the other vertices. It would be assumed each of the others are already connected.

share|cite|improve this answer

Assume there are V number of people.

Let each give handshake all others one-by-one, without any duplication

Person 1:
1. Person 1 handshakes with all other (V-1) people, so in total (V-1) handshakes are done
2. Lets remove Person 1, from the group again, to eliminate duplicate handshakes when we select other people

Person 2
1. Person 2 handshakes with all other (V-2) people, so in total (V-2) handshakes are done, V-2 is since we removed 1 person
2. Lets remove Person 2, from the group, to eliminate duplicate handshakes when we select other people

so on..

We get 1 handshake from last two people

--

So, we get (V-1), (V-2), etc. handshakes without any duplication

So, Sum of all handshakes = (V-1) + (V-2) ..
We know, N + (N-1) .. is N*(N+1)/2
Replacing N with V-1, we get
total handshakes = (V-1) * (V-1+1) /2 = (V-1)*V/2

Non-duplicate handshakes analogy is similar to Maximum number of edges, in a simply connected undirected unweighted graph from V vertexes

So, total edges in simple graph = (V-1)*V/2

Best of luck

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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