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.
Alternative explanation using combinations: • Number of Edges in a Complete Graph (...
Check out my lesson on the first theorem of graph theory: • The First Theorem of Graph Theory | G...
Check out the other explanation: • Number of Edges in a Complete Graph (...
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!
PURCHASE "A First Course in Graph Theory": https://amzn.to/31hgvvJ
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.
Vallow Bandcamp: https://vallow.bandcamp.com/
Vallow Spotify: https://open.spotify.com/artist/0fRtu...
Vallow SoundCloud: / benwatts-3
********************************************************************
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic
Watch video Edges in a Complete Graph (Using First Theorem of Graph Theory) | Graph Theory online without registration, duration hours minute second in high quality. This video was added by user Wrath of Math 24 October 2019, don't forget to share it with your friends and acquaintances, it has been viewed on our site 7,771 once and liked it 152 people.