Does this work? Proceeding by induction( base case is the same as in video), assume that tree of order k has size k-1 Now consider constructing graph of order k+1 we take the graph with k vertices that is a tree and then add a disconnected vertex v_k+1 to it. To ensure graph is connected now, add one edge to any of the other k vertices in the tree. Adding another edge ,however causes a contradiction since this would mean that the connected graph of order k+1 will have a cycle. Hence the number of edges for the graph of order k+1 is (k-1) + 1 = k. I think the argument is simliar to yours but mine takes an 'adding vertices' approach instead of deleting them.
Thanks for making videos. Your lessons always seem to help and are super clear to understand. A very underated channel since you always have brilliant delivery. :))
Thanks for watching, Kat, I’m glad the lessons have been helpful and I really appreciate your kind words! Let me know if you ever have any video requests! :)
Thanks for watching and you're right that the converse is true, but we have to specify that the graph is connected! I haven't proven it using spanning trees - though I'm sure that would work, but I did a different proof on it in today's lesson if you're curious: ua-cam.com/video/D1ZQAKnzXa4/v-deo.html
Thanks for watching and good question! All you need to do is find a counterexample. The converse of this statement is "A graph or order n and size n-1 is a tree." So to show it is false, find a graph that has one less edge than it has vertices and is NOT a tree! Note the result is close to true! This result IS true: "A connected graph of order n and size n-1 is a tree." Here is a proof: ua-cam.com/video/D1ZQAKnzXa4/v-deo.html Hope that helps!
Thanks for watching and for your question! Could you clarify your notation for me? Are you trying to show that, if e is an edge of G, then the clique number of G is less than or equal to the clique number of G-e, and that the clique number of G-e is less than or equal to the clique number of G plus 1? Or does the w(G) mean something else?
Here is my lesson discussing/proving the converse of this statement: ua-cam.com/video/D1ZQAKnzXa4/v-deo.html
Number of components
W is number of components of G (i.e omega)
kindly add this video as 66th video in graph theory playlist. Thank
Can't believe this awesome video doesn't have a lot like
I'm sure it will in due time. Thanks for watching! :)
Does this work?
Proceeding by induction( base case is the same as in video), assume that tree of order k has size k-1
Now consider constructing graph of order k+1
we take the graph with k vertices that is a tree and then add a disconnected vertex v_k+1 to it.
To ensure graph is connected now, add one edge to any of the other k vertices in the tree.
Adding another edge ,however causes a contradiction since this would mean that the connected graph of order k+1 will have a cycle.
Hence the number of edges for the graph of order k+1 is (k-1) + 1 = k.
I think the argument is simliar to yours but mine takes an 'adding vertices' approach instead of deleting them.
Thanks for making videos. Your lessons always seem to help and are super clear to understand. A very underated channel since you always have brilliant delivery. :))
Thanks for watching, Kat, I’m glad the lessons have been helpful and I really appreciate your kind words! Let me know if you ever have any video requests! :)
Thanks for adding related videos in the description. You made it really easy. Thanks Again.
Glad it helped! Thanks a lot for watching!
Thank you sir! For making useful videos 🙇
Thanks for these proofs like there aren't any other materials out there I found till now that explains these so clearly..
Glad to help - thanks for watching!
If we add a leaf to a tree, is it still a tree? so could we also use mathematical induction to prove that k+1 is true and just assuming that k is true
Yes, the converse of this statement is also true. This can be shown by considering spanning tree inside the connected graph.
Thanks for watching and you're right that the converse is true, but we have to specify that the graph is connected! I haven't proven it using spanning trees - though I'm sure that would work, but I did a different proof on it in today's lesson if you're curious: ua-cam.com/video/D1ZQAKnzXa4/v-deo.html
@@WrathofMath Yes i watched it your proof was similar to mine.
Thank you sir.... love and many respect from india...
You're very welcome and thanks for watching! Much love back!
Thank you so much for this video ! brilliant delivery
You're very welcome! Thanks a lot for watching!
Thank you so much ! well explained
My pleasure, thanks for watching!
Show that an n-vertex graph G is a tree if and only if G has no cycle and
has n − 1 edges.
Great work
Thank you!
n-1? More like "Nice videos, and learning is fun!" 👍
How to prove that the converse of this theorem is not true?
Thanks for watching and good question! All you need to do is find a counterexample. The converse of this statement is "A graph or order n and size n-1 is a tree." So to show it is false, find a graph that has one less edge than it has vertices and is NOT a tree!
Note the result is close to true! This result IS true: "A connected graph of order n and size n-1 is a tree." Here is a proof: ua-cam.com/video/D1ZQAKnzXa4/v-deo.html
Hope that helps!
@@WrathofMath Thank you so much, pls make more videos about graph theory, math majors like us needs you
super helpful thannk yoyu
Glad to help!
Hello sir, I want to solve this problem could u please help me..
Show that if e (E ) then w(G)
Thanks for watching and for your question! Could you clarify your notation for me? Are you trying to show that, if e is an edge of G, then the clique number of G is less than or equal to the clique number of G-e, and that the clique number of G-e is less than or equal to the clique number of G plus 1? Or does the w(G) mean something else?
@@WrathofMath w is number of components of G
@@mvarchanathulasi1190 deleting only bridge edges can only increase no. of component by1 .u can see by considering example of c3 graph