Graphs & Pigeonhole Principle: Two (or More) Vertices Have The Same Degree (Mathematics for CS)
5Join the Party! Today we have some fun exploring proving a basic claim in graph theory using the pigeonhole principle. We see a direct proof and a contradiction proof for the same party-themed claim (that has an equivalent formulation using graph theory), employing the pigeonhole principle!
Time Stamps:
0:00 Opening, Party Time with your friends (setup)
2:03 Claim: Some pair of people at the party are friends with the same number of people at the party.
4:15 Proof 1 (Direct)
15:50 Proof 2 (Contradiction)
24:20 Graph-theoretic equivalant formulation: When an undirected graph has at least two vertices, some pair of vertices have the same degree.
31:18 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
#mathematics
#combinatorics
#graphtheory