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

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.
Connected graphs with one less edge than vertices NEVER have cycles, and connected graphs with no cycles are called tree graphs; check out these lesson on them...
Intro to Tree Graphs: • Intro to Tree Graphs |...
Proof that a tree graph of order n has size n-1: • Proof: Tree Graph of O...
Proof that a connected graph with n vertices and n-1 edges is a tree graph: • Proof: Graph with n Ve...
◆ Donate on PayPal: www.paypal.me/wrathofmath
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+WRATH OF MATH+
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic

[@PunmasterSTP]

Minimal counterexample? More like "Magnificent lectures, with quality that's more than ample!"

[@LearningCS-jp4cb]

Didn't get the minimum order part of proof, but luckily i can understand alternate contradiction using same argument.

[@tchappyha4034]

Thank you very much for your elegant proof.

[@-Manasa-ij4bb]

Consider an undirected graph G that has n distinct vertices where each vertex has degree 2. Assume n≥3. What is the maximum number of circuits that G can contain? If all the vertices of G are contained in a single circuit, what is the maximum number of vertices that can be contained in an independent set?

[@imwatchingyou9975]

I don't know what to say

[@tifawine9113]

BUT the triangel has 3 sides. Why should be just 2 edges?

[@sufiyanbudye4275]

Neatly explained 👌

[@parasmittal3697]

Great proof , thanks a lot for this !!

[@rahulkhatav9089]

Good explanation. Hope it saves me for the exams 😅

[@abhistyadav9421]

How do you prove that after removing an end vertex the graph still remains connected

[@eddieadnan1]

Hello can you make a vdieo on Prufer code

[@Salman15474]

what a clever neat proof this was

[@tybargky461]

I am still confused lol

[@kanikasihag9881]

Hey!!could you pls make a video on the que:

[@mariyamsanayam1867]

Nice class

[@dogkansarac4889]

dont you think using induction is way easier than this proof?

[@monke9865]

Really appreciate your videos.