What is a Subgraph? | Graph Theory
ฝัง
- เผยแพร่เมื่อ 1 ก.ค. 2024
- What is a subgraph? We go over it in today's math lesson! If you're familiar with subsets, then subgraphs are probably exactly what you think they are. Recall that a graph G = (V(G), E(G)) is an ordered pair with a vertex set V(G) and an edge set E(G). Then, another graph H = (V(H), E(H)) is a subgraph of G if and only if V(H) is a subset of V(G) and E(H) is a subset of E(G). So, a graph H is a subgraph of G if and only if every vertex and edge in H is also in G. Thus, just like with subsets, every subgraph is a subgraph of itself. If a graph H is a subgraph of G, and H is not equal to G, we say H is a proper subgraph of G.
I hope you find this video helpful, and be sure to ask any questions down in the comments!
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
Music Channel: / seanemusic
I could cry 😭 this makes so much SENSE now! Thank you!!
So glad it helped! Thanks for watching, Kago! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
@@WrathofMath I’m watching the playlist as we speak 😭 you’re a godsend, thanks again!🤍
Flattering aside, you're validly and genuinely a qualified teacher, I personally fell in love with your method of teaching after watching this content just once.
Thank you so much, Adebayo! So glad you found it clear, and let me know if you ever have any questions!
Simple, comprehensive and straight to the point. Kudos
Thanks! Let me know if you have any questions, and check out my graph theory playlist if you're looking for more! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
soldering through. i enjoyed how you asked us to pause and think about what the answer to the purpose of the video is
Thank you so much for this! This was super helpful!
You make all the concepts so easy to understand. You actually have the qualities of a good teacher
Glad to hear it, thank you!
@@WrathofMath *read
Your videos are amazing. I really loved it.
If possible,could you solve some graph theory problems? just to know the different areas where graph theory could be applied.
Thank you, this was very helpful.
Thank you for clarifying. Great use of visuals and colours. Keep it up.
Thanks - glad it helped! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Let me know if you ever have any video requests!
Much clearer than my stats book! thank you :)
Thank you for the explanation, So clear!
May i ask about "what's subgraph complement"?
Amazing videos! any good books on math logic and graph theory basics?
Thanks a lot, you have completed a great work!
You're very welcome and thanks for watching!
Thank you so much. Great explanation.
You're very welcome, thanks for watching! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Mahn you’re awesome 👏🏻 super easy to understand.
Thanks a lot for watching and for your kind words! I'm glad it was easy to understand. Let me know if you ever have any video requests!
Great video and easy to understand. Your amazing 🤩
thank you so much, best teacher.
Thank you!
can subgraph only draw 2 dots? for your G example, is it correct only 2 dots, 1 and 2 given, without drawing the line??
Can you try proving that for a tree T with n vertices and a graph G for which holds that d(v) >= n' - 1 where n' >= n, T is a subgraph of G.
Thank you
Great work. Keep it up, please.
Thank you and I will! Let me know if you ever have any video requests!
Thank you sir for your good explanation
No problem thank you for watching! Check out my Graph Theory playlist if you're looking for more lessons on the topic, many more coming soon! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
how many subgraphs does a graph have in total and how to find all the subgraphs of a graph?
Hi Sean, I have a test coming up, do you do tutoring?
hey sean kindly make a video on isomorphic & non-isomorphic graphs and also on proper and improper subgraph. Your content is quite helpful and easy.
Thanks for watching Arish, and the isomorphic graphs lesson is long overdue! Thanks for the requests, I am glad the content has been helpful and I'll do those lessons soon!
Here's the lesson on proper and improper subgraphs! Thanks again for the request, more are on their way! th-cam.com/video/ektwvSqL0Vw/w-d-xo.html
Thank you for the video :)
My pleasure! Thanks for watching!
Nice video bro 🤜
Thank for clearing my topic 😍
Glad to help! Thanks for watching and check out my graph theory playlist if you're looking for more! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
I love your voice❤️
and the content 😌 is really really good!!
Thanks sir!
from india
Thanks so much! I am glad you're finding it useful and let me know if you ever have any questions! 😌
what if the positions of the vertices changed and the edge linked to respective pairs of vertices are equal? are they still subgraph of original graph? please explain. thanks
Thanks for watching and you are referring to drawing the graphs differently, right? The drawing of a graph is mostly a convenient way to represent the edge and vertex sets, so drawing it differently does not change the graph at all - so yes, still a subgraph. The way we draw the graphs does come more into focus when we discuss planar graphs, and of course it's always nice to have a nicer drawing of a graph rather than an unnecessarily ugly one, but it does not really matter!
Hi, i have one question, if the vertex or edge is not at the original position as the G, does it consider as a subgraph?
Thanks for watching and great question! Yes, if G is a graph, what defines, say H, as a subgraph of G, is that H is a graph, and the vertices and edges of H are all in G. The way H is drawn does not affect whether or not it is a subgraph. Hope that helps!
@@WrathofMath thanks sir. I appreaciate your reply. Thanks a lot. I pray that you are doing well!!
thank u🖤🖤🖤🖤
My pleasure, thanks for watching! If you're looking for more graph theory, check out my playlist! th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
Thank you sir
You're welcome, thanks for watching!
in comparison of G and J graph you said that the vertex set of both are same but it is not i guess, g has 6 vertices and j has 5. can you please clear it out if i am wrong?
I think you might have misheard him. In any case, it's fine for a subgraph to have fewer vertices, as long as it doesn't have any edges not present in the original graph.
Subgraph? More like "Super videos that are where it's at!"
beautiful 🌈
Thank you!
5:26
Thanks for watching!
الله يسعدك يا شيخ
شكرا لك!شكرا لك!
i have a doubt are single vertices subgraphs
Thanks for watching and for your question! They can be, yes. So long as the vertex is in the graph G, then it is a subgraph of G. If H = ( { v }, { } ) is a graph, where we have one vertex v and an empty edge set, it is by definition a subgraph of G if { v } is a subset of G's vertex set since of course { } is always a subset of G's edge set, since the empty set is a subset of every set.
is null graph a subgraph of any graph??
That's a great question! It depends what you mean by null graph. I use the word null graph to refer to the graph with no vertices and no edges. This graph is not always considered a graph, but if you do consider it a graph, since its vertex and edge sets are empty, it is by definition a subgraph of every graph (since the empty set is a subset of every set).
If, on the other hand, by null graph you mean a graph with one vertex and no edges (I usually call this the trivial graph), it is not a subgraph of every graph because of vertex labels. For example, we may say G = ( {v}, { } ) and H = ( {u, w, x}, {u, w} ). Then G is not actually a subgraph of H because G has the vertex v, but v is not anywhere in H. However, the trivial graph is isomorphic to a subgraph of every graph. If you just consider a single vertex in a graph, and no edges, that subgraph with that one vertex is isomorphic to the trivial graph. Does that make sense?
Here is my graph theory playlist if you're looking for more: th-cam.com/play/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH.html
@@WrathofMath Understood completely. Thanks for the wonderful explanation. Will definitely checkout the graph theory playlist.
Which song is the outro? Someone, please help
Thanks for watching and it is a song I wrote called "Turn Over". Unfortunately there is no finished version anywhere. However, you can find more of my music on this channel: th-cam.com/channels/OvWZ_dg_ztMt3C7Qx3NKOQ.html and this channel: th-cam.com/channels/BDXtKCGkvF-bWfuf6JNDiQ.html
@@WrathofMath Can you please send me Turn Over, I watch this video again so I can listen to the song, here's my email.
arron.ahuja@gmail.com
Looking forward to it!
Hi sir,
I have some help
I have to submit graph theory for field studies ,
I have to took topic is subgraph
So give sum idea about sub graph please 🥺 sir pls help me
Dude you are making it complicated. It is just a subgraph, that means just a part from the original graph G. You need to draw them at start so its clear what are you talking about and explain after that. And you can't start with 5 vertices like what the hell.
start with K3 graph. For example if you have a graph with vertices V={a,b,c}, and edges e={ (a,b) , (b,c) , (c,a) } one of the possible subgraphs is vertices={a,b} and only one edge to connect them e=(a,b).
This is used for example when you are working with larger graphs so you make a subgraph only with the vertices you need. For example if it is a map of the world and you are asked do find the borders of the countries in Europe so you cut off the other continents because you want to focus on what you need to make it simple, so you make a subgraph only of Europe.
Thank you for your feedback, and I'm sorry to hear this lesson was not effective for you! There are a number of reasons I occasionally choose to go into a definition before an example, but I do think people generally prefer a quick example first. I also wish I had included smaller examples in this lesson so that I could have more easily included multiple instead of just one. Occasionally I am unhappy enough with a past lesson to take it down and make a new one, but that is not the case with this lesson; of course no lesson is perfect. For anyone who watches this video in the future, and sees and agrees with your comment, I offer this lesson by Sarada Herke, which has a structure closer to what you describe, and I hope will help anyone who finds this lesson inadequate.
th-cam.com/video/dPHkyRvLtIU/w-d-xo.html
Thanks for watching!
For what it's worth, I thought the video was straightforward enough.