Number of Edges in a Complete Graph (Using Combinations) | Graph Theory, Combinatorics

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, the first lesson on a whiteboard!

Remember that a complete graph K_n is a graph with n vertices and edges joining every pair of vertices. So, to count the edges in a complete graph we need to count the total number of ways we can select two vertices, because every pair will be joined by an edge!

How many ways can we select two vertices from a collection of n vertices? Since order doesn't matter, the answer is a binomial coefficient, n choose 2. This is equal to n! / ( 2!*(n-2)! ).

SOLUTION TO PRACTICE PROBLEM:

The graph K_5 has (5*(5-1))/2 = 5*4/2 = 10 edges.

The graph K_7 has (7*(7-1))/2 = 7*6/2 = 21 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...

[vibodhj]

Awesome lecture with a lot of humor in it! Nice to see you transition from a faceless Youtube math tutor to a facially expressive Youtube math tutor. Thanks for the tutorials!

[PunmasterSTP]

A unit on graph theory and this playlist is one heck of a great combination!

[WrathofMath]

Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!

[JannahLoraineCanayon]

I LOVE YOU SIR!!!! currently taking up this subject and because of you I can answer my module already. THANK

[Dr.Cassio_Esteves]

Awesome.
I managed to prove it using induction, but this prove is much more interesting.

Sorry any mistakes, my English is a work in progress.

[Bryceeeeeeeez]

How would you determine how many vertices there are; given the amount of edges?

[mamamia-kt]

I go to Ivy League and I rely on this series to get me through graph theory. I should be paying you instead. :D

[nehaharidas]

Can you do a session on Crown Graphs, Please?

[TechieCube]

Let Kn denote the complete graph on n vertices, with n ≥ 3, and
let u, v, w be three distinct vertices of Kn. Determine the number of
distinct paths from u to v that do not contain the vertex w.
sir please give solution

[Awaseme]

Hey WoM thank you for the videos! Why did you switch from digital to analog?

[akshithamnair]

Number of edges for K5=10
Number of edges for K7=21