Proof: Graph with n Vertices and n-1 Edges is a Tree | Graph Theory

A connected graph with n vertices and n-1 edges must be a tree! We'll be proving this result in today's graph theory lesson! We previously proved that a tree graph with n vertices must have n-1 edges, so this gives us a characterization of tree graphs as follows.
A connected graph is a tree if and only if it has one less edge than vertices.
Proof that trees have one less edge than vertices: • Proof: Tree Graph of O...
Proof that edges are bridges iff they lie on a cycle: • Proof: An Edge is a Br...
◆ Donate on PayPal: www.paypal.me/...
◆ 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!
********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.
Vallow Bandcamp: vallow.bandcam...
Vallow Spotify: open.spotify.c...
Vallow SoundCloud: / benwatts-3
********************************************************************
+WRATH OF MATH+
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic

[@WrathofMath]

Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions!
ruclips.net/channel/UCyEKvaxi8mt9FMc62MHcliwjoin
Graph Theory course: ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Graph Theory exercises: ruclips.net/p/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L

[@isaacwritescode]

What a legend🛐

[@WrathofMath]

I do my best - thank you for watching!

[@mgames1710]

Very clean explanation, thank you so much!

[@WrathofMath]

My pleasure, thanks for watching! If you're looking for more graph theory, check out my playlist! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@Fearnotsforlove]

This was a great and clear explanation! Thank you!

[@mishabalakirsky243]

Was really helpful, thanks a lot!

[@WrathofMath]

Glad it helped!

[@richardhunter132]

so, if I have a graph, all I need to do is count the number of vertices and the number of edges, and as long as the number of edges is one less than the number of vertices, then I have a tree?

[@no_money_funny]

good job man

[@WrathofMath]

Thank you!

[@parthajyoti743]

Hey plz make video on Ramsey number

[@alexandradepillis-lindheim7039]

This was awesome! thank you:)

[@WrathofMath]

So glad it was helpful, thanks for watching! Check out my graph theory playlist if you're looking for more, and let me know if you ever have any questions! ruclips.net/p/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@fio6143]

rap of math. love it tho. keep it up :)

[@WrathofMath]

Thank you - I will!

[@Aman_iitbh]

can we say directly when we first time delete edge from cycle that the remaining graph is connected and deg is still n but edge is n-2 so its violating theorem that any connected graph of order n has size atleast n-1

[@LearningCS-jp4cb]

Are you studying in an IIT from India? If so, are you learning graph theory for college exam or something else?

[@foocaha3990]

how to prove that a graph with 5 vertices and 4 edges is not necessary to be a tree if it is connected?

[@foocaha3990]

if i use kite shape without cross line and use just one straight line in kite shape is it correct ?

[@itv5610]

That's not possible for a connected graph. That is what was proved in this video.

[@browse101]

IT IS a tree

[@saketkumar4972]

great, the video could have been smaller tho

[@rexfordboakye5312]

Sounds great

[@WrathofMath]

Thanks!

[@psinghcpr]

Can you make a video on mantel and turan's theorem. If yes then please prove it with zykov symmetrization.

[@WrathofMath]

Thanks for watching and for the requests! I will certainly do videos on Mantel's and Turan's theorem, I'll try to do them sooner than later. I am not familiar with Zykov Symmetrization, do you have any references you'd recommend on the topic?

[@psinghcpr]

@@WrathofMath Thanks . You can refer to david conlon ' s notes or yufei Zhao's notes on graph theory and additive combinatorics . The later has video lectures available on mit ocw youtube channel.
Hope you check them out.

[@keithplays1184]

👍👍👍👍

[@WrathofMath]

Thanks for watching, Keith!

[@PunmasterSTP]

Ah, another edgy lecture!