Today we see how we can apply the averaging principle to prove a graph-theoretic claim. Notice how we use it here to guarantee the existence of a vertex with a degree at most the average degree (which we bound, using the Handshaking Lemma, which we prove here: https://youtu.be/p5il-zRyjAI).
Time Stamps:
0:00 Opening and reminder of averaging principle
0:42 Theorem: Graphs with less than n-1 edges are disconnected.
2:12 Proof of claim, using the averaging principle.
22:57 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
2