Edges in a Complete Graph (Using First Theorem of Graph Theory) | Graph Theory

How many edges are in a complete graph? This is also called the size of a complete graph. We'll be answering this question in today's video graph theory lesson, providing an alternative explanation to the one we did in a previous lesson, because it’s always good to be able to verify our solutions with alternative reasoning!

Remember that a complete graph K_n is a graph with n vertices and edges joining every pair of vertices. Thus, each vertex is adjacent to all other vertices. So if a complete graph has n vertices, each vertex is adjacent to n-1 vertices, and thus has a degree of n-1. We can also think of the degree of a vertex as being the number of edges incident to the vertex. Notice each edge contributes 2 to the total degree count of a graph because each edge is incident to 2 vertices. So if we add up all the vertex degrees in a graph, we get two times the number of edges (this is The First Theorem of Graph Theory).

Thus, since each of the n vertices in the complete graph K_n has degree n-1, the sum of the degrees is n*(n-1). If the edge set is E, then we have n*(n-1) = 2*|E| and therefore |E| = (n*(n-1))/2.

SOLUTION TO PRACTICE PROBLEM:

The graph K_9 has (9*(9-1))/2 = 9*8/2 = 36 edges.

The graph K_10 has (10*(10-1))/2 = 10*9/2 = 45 edges.

If you're taking a course in Graph Theory, or preparing to, you may be interested in the textbook that introduced me to Graph Theory: “A First Course in Graph Theory“ by Gary Chartrand and Ping Zhang. It’s a wonderful text! You can purchase this book through my Amazon affiliate link below! Using the affiliate link costs you nothing extra, and helps me continue to work on Wrath of Math!

I hope you find this video helpful, and be sure to ask any questions down in the comments!

********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.

********************************************************************

+WRATH OF MATH+

Follow Wrath of Math on...

[TheCuriousLifeOfCode]

Thank YOU so much for this! Great Timing :-D

[vibodhj]

4:25 You spelt 'often' as 'of tan' instead of 'o fun' but you're British I suppose. Hmm..Leaving aside the trivial matters, its so interesting to know that a single problem can have so many solutions and just by changing our perspective of looking at the problem, we can invent a new solution. This is really cool. Btw your whiteboard is too shaky, maybe you should put something solid behind it to support it. Thanks for making my day..

[mangubatdarwin]

Good morning, can I ask ypur help, with this problem

Show that if G is a graph with δ(G) ≥ 2 containing a cut-vertex of
degree 2, then G has at least three cut-vertices

[sanampuri]

A complete graph has 190 edges. How many vertices does the graph contain?

should I use n^2-n-380=0?

[axelgayondato]

Hi! Do you have a video about weighted graphs?

[rikupt]

Hey, are all complete graphs isomorphic?