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

• Charles Stark
In summary, this student is trying to prove that all vertices of a complete graph have a degree of (n-1). He is using the degree sum formula and the edge formula for a complete graph to get his result. However, he may not have explained the reasoning behind his methods very well.

## Homework Statement

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

## Homework Equations

∑ deg(v) = 2|E|

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

## 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:
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.

Charles Stark said:

## Homework Statement

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

## Homework Equations

∑ deg(v) = 2|E|

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

## 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)
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.
Charles Stark said:
∴ 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.

Mark44 said:
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!