The Handshaking Lemma (Graphs: Algorithms & Theory)
6A valuable concept in graph theory is the degree of a vertex, and the Handshaking Lemma. While we may revisit this topic further if there is interest, I wanted to introduce this cute but powerful concept to you. It is used often in explaining basic analysis techniques for algorithms, depending on the way the graph is represented, and sometimes in cute counting tricks!
In this video, we see how we could apply the Handshaking Lemma to figure out how many edges at most a simple graph can have and what a complete graph is!
Time Stamps:
0:00 Opening, definition of degree of a vertex
4:02 Handshaking Lemma and a proof
14:45 What is the maximum number of edges a simple graph can have? What is a complete graph. Application of Handshaking Lemma.
24:48 Closing
Have a beautiful day!
Supporters (to date of publication, by tier (top to bottom)):
----------------------------------------------------------
Patreon Supporters (General Support):
Draikou
Patreon Supporters (Basic Support):
Patreon Supporters (Supporter Access!):
Eric R
-----------------------------------------------------------
Become a supporter today! To support my work and mission to provide free or accessible Computer Science education (especially in theory), subscribe to the channel, share my videos. Please donate and contribute to support my work for more content:
PATREON: https://www.patreon.com/PageWizard
SUBSCRIBESTAR: https://www.subscribestar.com/drpage
PAYPAL: https://paypal.me/pagewizard
Follow also at:
FACEBOOK: https://www.facebook.com/DanielRPage
TWITTER: https://twitter.com/PageWizardGLE
QUORA: https://www.quora.com/profile/Daniel-R-Page
TWITCH: https://www.twitch.tv/pagewizard
#ComputerScience
#Algorithms
#graphtheory