Graph Theory Proof

  • #1

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:

Answers and Replies

  • #2
473
13
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
34,688
6,394

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.
 
  • #4
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!
 

Related Threads on Graph Theory Proof

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
542
  • Last Post
Replies
21
Views
6K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
0
Views
4K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
5
Views
798
  • Last Post
Replies
5
Views
2K
Top