Graph Theory Proof: Prove All Vertices of Kn Have deg(v)=(n-1)

[Charles Stark]

Homework Statement

Prove that all vertices of a complete graph K_n have deg(v) = (n-1)

Homework Equations

∑ deg(v) = 2|E|

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

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 K_n,

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

K_n has n vertices so,

deg(v₁) + deg(v₂) + . . . . + deg(v_n) (1/n) = (n-1)

∴ Each vertex , v, has degree (n-1)EDIT: The degree sum formula was mistakenly labeled as the Handshaking lemma.

 

[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.

 

[Mark44]

Homework Statement

Prove that all vertices of a complete graph K_n have deg(v) = (n-1)

Homework Equations

∑ deg(v) = 2|E|

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

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 K_n,

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

K_n has n vertices so,

deg(v₁) + deg(v₂) + . . . . + deg(v_n) (1/n) = (n-1)

The above is incorrect. The 1/n factor is multiplying only the last term, deg(v_n. I imagine that you meant this:
[deg(v₁) + deg(v₂) + . . . . + deg(v_n)] (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.

∴ Each vertex , v, has degree (n-1)EDIT: The degree sum formula was mistakenly labeled as the Handshaking lemma.

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.

 

[Charles Stark]

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.

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!