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! ru-vid.com/show-UCyEKvaxi8mt9FMc62MHcliwjoin Graph Theory course: ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Graph Theory exercises: ru-vid.com/group/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L
I do not have words to express my gratitude towards this channel coz am covering everything on my discrete and calculus courses by this.Thank you so much sir and one small request !Plz if u can keep doing the videos lively like this not using screen and just writing because it gives a feel that we are really learning in your class.
Wrath of Math has really drive me crazy. I can't image to might have such a gleaming and audible tutor with well oriented presentation ever. I thank you sr.
00:29 Hamiltonian Cycle: A Hamiltonian cycle in graph theory is a cycle that contains every vertex of the graph. 02:00 Hamiltonian Path: Deleting an edge from a Hamiltonian cycle results in a Hamiltonian path, a path that contains every vertex. 03:48 Hamiltonian Path vs. Cycle: Having a Hamiltonian path doesn't guarantee a Hamiltonian cycle; the converse is not necessarily true. 05:11 Connectivity: A necessary condition for a graph to be Hamiltonian is that it must be connected. 05:38 Cut Vertices: A graph must not have cut vertices (vertices that disconnect the graph when deleted) to have a chance of being Hamiltonian. 07:53 Degree Condition: Another necessary condition is that a graph cannot have a vertex with a degree less than 2; degree 1 vertices pose problems. 08:46 Always Hamiltonian Graphs: Cycle graphs and complete graphs (with at least three vertices) are always Hamiltonian. 10:22 Sufficient Conditions: There are sufficient conditions for a graph to be Hamiltonian, like Ore's Theorem, which will be covered in another
I think I'm just going to watch this channel as my entertainment for the next few months :P by the time I get through all of this I'll be a good graph theorist (seeing as I do have homework that forces me to be as well)
for a complete bipartite graph to be a hamiltonian graph we need an equal number of vertices in each set and the minimum value of m and n have to be 2.
Sir, thanks a lot. Please prove the result "Let D be a simple n-vertex digraph. Suppose that for every pair of vertices v and w for which there is no arc from v to w, outdeg(v) + indeg(w) ≥ n. Then D is Hamiltonian.
You're welcome, thanks for watching! I try to be very precise in my language and explanations, I think that's very important. And when I am not being precise, it gets thrown in the trash!
Haha I used to render my whiteboard videos with DaVinci Resolve, which had those weird glitches! I still use Resolve for the lessons not on the whiteboard, but I use Final Cut Pro for my whiteboard videos now and it has no such demons thankfully! Thanks for watching!
@@WrathofMath hehe nice. Great Videos btw. Well explained and edited. Keep up the good work and also try branching out into other subtopics as well. The internet could use those.
Thanks, Donald! If you're looking for more Graph Theory, be sure to check out my Graph Theory playlist! ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
Thank you, glad to hear it! If you're looking for more graph theory, check out my graph theory playlist! ru-vid.com/group/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH
God willed it! As amazing as a wonderful explanation! But me from your computer and you show your face it would be so much greater than board! Because from you computer you use different styles and you make it is easier to understand even a new born can understand from the computer! Still I do appreciate your assistance
Thank you for watching and for the kind words! I've considered combining a face cam with the digital lessons, but there are a few difficulties with that due to my set up. I do not know if I will do it in the future, but perhaps! Thanks for letting me know what you'd like to see!
If you have a graph that is a square lattice of 3x3=9 nodes, is that a hamiltonian graph? I can't find the hamiltonian cycle even though it is connected and there are no cut vertices. A 3x4 lattice works just fine though.
Thanks for the clarification! Are you sure you've stated the result correctly? As it stands, the result is not true. Consider two K3 graphs, with one shared vertex (as if we drew two triangles that share a single vertex). The minimum degree is 2, there are 5 vertices, but no Hamilton cycle (we'd have to travel across the shared vertex multiple times if we tried to visit every vertex in the graph.
thank you so much for this insightful video!! it helped me out SO MUCH. thank you thank you thank you!!! but one thing i don't get is at 4:02--why can't i add a link from 4 to 1? it's similar to how You'd done the (a,b,c,d,a) cycle where a and c had a link together above b.
You're very welcome and I am so glad it helped! Thank you for watching and for your question. The context there is I had just explained that if we have a Hamiltonian cycle, we can delete an edge to have a Hamiltonian path. Don't misunderstand that though - the point is not that we can change a cycle into a path, the point is that the path is CONTAINED within the cycle. Then I show the example at 4:02, to demonstrate that having a Hamiltonian path does NOT guarantee a cycle. As you point out, we could add an edge to the path to get a Hamiltonian cycle, but that would be changing the graph. The point was that the graph contains a Hamilton path, but no Hamilton cycle, whereas if a graph contains a Hamilton cycle, it must also have a Hamilton path. Does that clear it up?
Thanks OP for asking it and thanks Wrath of Math for explaining it. I too got confused at this part. Btw your videos are helping me a lot. Thank You so much! :D
I know Im asking the wrong place but does anyone know of a tool to get back into an instagram account..? I somehow forgot my account password. I love any tips you can give me!
4:08 Isn't the converse of deleting an edge from a h.c to get a h.p adding an edge to a h.p to get a h.c ? If so isn't it possible to get a h.c b connecting the first and last vertex on the path to get a cycle?? Confused !
Thanks for watching and for the question! We have to make sure we're clear on the statement being made. This is true: If a graph contains a Hamilton cycle, then it contains a Hamilton path; since an edge can be deleted from a Hamilton cycle to obtain a Hamilton path. Then, the converse is: If a graph contains a Hamilton path, then it contains a Hamilton cycle. The converse is not true because a graph can contain a Hamilton path without having a Hamilton cycle. Consider any path graph, for example. They all have Hamilton paths, but none of them have Hamilton cycles. So you're right we can add an edge to a Hamilton path to get a Hamilton cycle, but that edge isn't guaranteed to be there in a graph that has a Hamilton path, does that make sense? We're talking about these structures being in graphs, not just about the structures themselves.
can you please solve this question ? Prove or give a counterexample: If every vertex has at least 3 neighbors, then the graph has a cycle of length at least 4, i.e., a cycle consisting of at least 4 vertices.
Thanks for the question! Here are two lessons in which we use ideas similar to that necessary to prove your claim. Result about paths: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-7bBTpSVa9tc.html Result about minimum degree implying a cycle: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-FLqeKSAPlwM.html A lesson proving a generalization of your claim comes out two and a half hours from now! So give it a try yourself and then check out the lesson when it comes out! :) If you're not subscribed already, you can subscribe to make sure you see it in your feed.
@@WrathofMath I watched this video but it's getting mix up , can you please give any example related to algorithm that you explained in this video. thanks
@@WrathofMath I watched second video also but it's like explaining there is a cycle but my question is about , if a vertex has n neighbors then cycle is of n+1 vertices , in my mind I can do it with 1 vertex having 3 neighbors but to make a cycle there must be a path between every adjacent vertices.
This lesson proves a generalized version of your statement: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE--8QRcpbI6J8.html Let me know if you have any questions!
Thanks for watching and that's funny! It's a fine looking set, but I find some of the pieces a little weird. Like the knight has a rounded bottom rather than a flat one. It can rock around a little bit on the board, which is quite odd since none of the other pieces are like that.
Good day sir, i have a question, I hope you can help me,, If the two graphs, A and B are both Hamiltonian, how to prove that the join of these two graphs is also Hamiltonian?
What set of assumptions are you working with? Are you assuming A and B are completely different graphs? There are three importantly different cases I can think of. 1. A and B are completely disjoint graphs, they have no vertices in common and thus no edges in common. 2. The vertex set of A is a subset of the vertex set of B (or vice versa). 3. A and B have some vertices in common, but neither vertex set is a subset of the other. If you're trying to prove the result in the first situation (which I am guessing is most likely), you want to try constructing a Hamiltonian cycle in A join B by traversing the Hamiltonian cycle you know exists in A, but right before you finish the cycle, go to the Hamilton cycle of B, which you know you can do because every vertex of A is adjacent to every vertex of B when they are joined. Then travel through the Hamilton cycle of B but right before finishing it, finish your big Hamilton cycle by returning to the vertex of A that you began at. If you're trying to prove the result in the second situation, it is fairly trivial. Say every vertex of A is also a vertex of B. Then B is a spanning subgraph of A join B, and so since B is Hamiltonian, we know A join B is also Hamiltonian. If you're trying to prove the third result, that is definitely a bit messier. I'm not immediately sure how to go about it, maybe induction on the number of vertices A and B have in common, but I'm not sure that would be helpful or necessary, since it may be difficult to use our induction hypothesis in that sort of situation.
Thanks for watching, Bharatha! I'd be happy to do a video about girth, but what specifically do you want to know relating to girth and 4-regular graphs?
Design a graph that has a Hamiltonian cycle but does not have an Euler tour. You need to explain why the graph has no Euler tour. can anybody help me to solve this question?
Thanks for watching and what is the definition of Euler tour you're using? Do you mean a walk in the graph that contains every edge exactly once (often called an Euler path)? Or do you mean a closed walk in the graph that contains every edge exactly once (often called an Euler circuit)? Or something else?
Consider any normal cycle, and then consider Euler's circuit theorem we prove here: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-wC99T3aVDKQ.html If we have a cycle (every cycle is 2-regular), and then add any edge to it, joining nonadjacent vertices, it is still Hamiltonian (just travel around the outer edges of the cycle), but it is not Eulerian since two of our vertices have odd degree (the ones we added an edge between). Does that help?
Thanks for watching! I mention complete bipartite graphs at the end of the video, and in the description I provide an explanation as to what complete bipartite graphs are Hamiltonian and why. Would you like a lesson on this topic?
After over 350 videos, you're the first person to make reference to what I have been saying at the end of every single lesson! It made me smile to see that!
