Graph Theory Proof

1. Jan 5, 2015

Charles Stark

1. The problem statement, all variables and given/known data
Prove that all vertices of a complete graph Kn have deg(v) = (n-1)

2. Relevant equations
∑ deg(v) = 2|E|

|E| = ½(n)(n-1) for Kn

3. The attempt at a solution
I may have over thought this but this was my initial path at a formal proof.

Using the degree sum formula above and the formula for |E| for Kn,

∑ deg(v) = 2|E| = n(n-1)

Kn has n vertices so,

deg(v1) + deg(v2) + . . . . + deg(vn) (1/n) = (n-1)

∴ Each vertex , v, has degree (n-1)

EDIT: The degree sum formula was mistakenly labeled as the Handshaking lemma.

Last edited: Jan 5, 2015
2. Jan 5, 2015

Joffan

Interesting approach... it feels like you are using more advanced results to try to prove a simpler result, though - and that simpler result was perhaps used to prove the more complex results.

"A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge"
... that should be enough foundation to build your proof on.

3. Jan 5, 2015

Staff: Mentor

The above is incorrect. The 1/n factor is multiplying only the last term, deg(vn. I imagine that you meant this:
[deg(v1) + deg(v2) + . . . . + deg(vn)] (1/n) = (n-1)

In any case, what's your justification for dividing by n? It seems to me that this gives you the average number of vertex degrees.
In a complete graph with n vertices, each vertex must be connected to each other vertex. Thus, each vertex is connected to n - 1 vertices, so for each vertex v, deg(v) = n - 1. I'm not sure if you need to go into any more detail than this.

4. Jan 5, 2015

Charles Stark

Ah ha! I just saw the degree sum formula and the edge formula for a complete graph and tried connecting the two to get the result I needed. I should have just went back to the definition of a complete graph. Derp!