Proof: Connected Graph of Order n Has at least n-1 Edges | Graph Theory

Описание: Support the production of this course by joining Wrath of Math to access all my graph theory videos!
   / @wrathofmath  
🛍 Check out the coolest math clothes in the world: https://mathshion.com/

Graph Theory course:    • Graph Theory  
Graph Theory exercises:    • Graph Theory Exercises  

Get the textbook! https://amzn.to/3HvI535

A connected graph of order n has at least n-1 edges, in other words - tree graphs are the minimally connected graphs. We'll be proving this result in today's graph theory lesson!

We'll be using a special type of contradiction proof called a proof by minimum counterexample. If we assume that there is a graph contradicting our claim, we can consider one such graph of minimum order, then we will show that this "minimum order counterexample" is actually not a minimum order counterexample, producing a contradiction and proving our claim.

Intro to Tree Graphs:    • Intro to Tree Graphs | Trees in Graph Theo...  
Proof that a tree graph of order n has size n-1:    • Proof: Tree Graph of Order n Has Size n-1 ...  
Proof that a connected graph with n vertices and n-1 edges is a tree graph:    • Proof: Graph with n Vertices and n-1 Edges...  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu