Hi math01-ga,
A complete graph with n vertices always has n*(n-1)/2 edges.
This can be simply deduced by the fact that in a complete graph with n
vertices, every vertice is connected to the n-1 other vertices. So
that way we count n*(n-1) edges. Of course we counted every edge two
times that way, since every edge is connected to 2 vertices.
A mathematical proof can be constructed using the induction theory.
I'm assuming you're familiar with the concept of mathematical
induction. If this isn't the case, I provided some additionnal links
explaining induction theory.
The proof: Proof by induction on n. Let P(n) be the predicate, A
complete graph on n vertices has n(n-1)/2 edges.
Base case: P(1) is true because a complete graph on a single node has
no edges and 1(1-1)/2=0.
Inductive step: For n > 1 assume that P(n) is true in order to show
that P(n+1)
is true.
Let G(n) be a complete graph on n vertices. P(n) says that a complete
graph on n vertices has n(n-1)/2 edges. Thus G(n) has n(n-1)/2 edges.
If we add a new node x to G(n) and add n edges, one from each node in
G(n) to x, then we have created a complete graph on n+1 vertices. Call
this graph G(n+1). The number of edges in G(n+1) is equal to the
number of edges in G(n), n(n-1)/2 plus the number of edges we added,
n. Therefore the number of edges in G(n+1) = n(n-1)/2+n, which is
n(n+1)/2.
Thus P(n) => P(n+1) and by the principle of mathematical induction,
a complete graph on n vertices has n(n-1)/2 edges.
So if we apply this to a graph G(100) with 100 vertices, we would need
to add 100*99/2 edges, minus the 600 already existing edges. In other
words, we would need to add 4350 edges to turn it into a complete
graph.
If you need any further explanation, just let me know.
Best regards,
rhansenne-ga.
Search terms used: "complete graph" "induction" "edges" "vertices"
The proof by induction, as well as an illustration can be found here
(proof #4 on the page):
http://www.cs.dartmouth.edu/~cs21/midterm1_sol.pdf
Some links on mathematical induction:
Google Search on Mathematical Induction:
://www.google.be/search?q=%22mathematical+induction%22
Understanding Mathematical Induction:
http://www.cc.gatech.edu/people/home/idris/AlgorithmsProject/ProofMethods/Induction/UnderstandingInduction.html
Mathematical Induction by Peter Suber
http://www.earlham.edu/~peters/courses/logsys/math-ind.htm
Mathematical Induction at California State University
http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html
Examples of Mathematical Induction at CSUSB:
http://www.math.csusb.edu/notes/proofs/pfnot/node10.html |
