Hi Trev, for the last question when we try to find a homomorphism of K5, you added in the vertex 'e' by subdividing the edge (bf) into (be) and (ef). This eliminates the edge (bf) in the original graph where b and f were connected directly by the edge (bf) and also (be),(ef). Does it not matter that we just eliminate that edge?
I agree, It would mean that b has degree of 4 and f has degree of 5, but the original graph has b and f as 5, 6 respectively. I just added in an edge to my own copy as It is correct.
Since K5 is a complete graph and non planar and the notation for a complete graph is Kn, can we say that every complete graph where n > 4 is non planar?
What about this criteria: For every planar Graph G = (V, E) wtih |V | = n, |E| = m ≥ 3: m ≤ 3n − 6 and For every planar Graph G= (V, E) with |V | = n, |E| = m ≥ 3 and without cycles of length 3: m ≤ 2n − 4 Does this work or are there problems?
Thanks for your nice lectures. May I know is an empty graph (a graph with no edges) a planner graph? How about graph G that is the union of an isolated vertex and a complete graph of order 2, is G planner? Thank you
(1) Yes, by definition, an empty graph is planar. (2) What do you mean by a complete graph of order 2? If you are referring to a complete graph with 2 vertices (which is essentially an edge), then yes, it is planar.
When you subdivide a graph, the degree of a vertex may change. Subdividing a graph involves replacing an edge with a new vertex and two new edges. The new vertex is inserted along the original edge, splitting it into two separate edges.
Hello Trev! The homomorphism concept u explained in the beginning does not seem correct to me when I compare it to the one explained here: th-cam.com/video/RatkBWHUSqo/w-d-xo.html . Are you sure that H is homomorphic to G?? Can't find a proper vertex maping function!!
Euler's forumla is only good for checking if the current drawing of the graph is planar or not. It won't tell you if there is a different drawing of the graph that is planar which is the hard part.
![[Discrete Mathematics] Euler's Theorem](http://i.ytimg.com/vi/miAyelTI5sQ/mqdefault.jpg)
![[Discrete Mathematics] Euler's Theorem](/img/tr.png)
![[Discrete Mathematics] Vertex Degree and Regular Graphs](http://i.ytimg.com/vi/k7ThfZIT_ac/mqdefault.jpg)
11:39 "I am blessed with knowing the answer" , the superpower which I want for my exams lol
6:20 LMAO was not expecting to hear sexy mathematician in a planar graph video
same lmfao
"I cant do it thats why its not planar" and "kuratowski is a very very sexy mathematician" LOL
Very well explained, thanks!
Hi Trev, for the last question when we try to find a homomorphism of K5, you added in the vertex 'e' by subdividing the edge (bf) into (be) and (ef). This eliminates the edge (bf) in the original graph where b and f were connected directly by the edge (bf) and also (be),(ef). Does it not matter that we just eliminate that edge?
I agree, It would mean that b has degree of 4 and f has degree of 5, but the original graph has b and f as 5, 6 respectively. I just added in an edge to my own copy as It is correct.
I can already see the A on my Discrete Math course, Thanks a lot man!!
love these videos, far more helpful than other channels, but the kuratowskis theorem section is marked kura taos keys in the timeline
It would be really helpful if you put timestamps. Thanks!
If I pass my Discrete test on Wednesday it'll be thanks to this
Since K5 is a complete graph and non planar and the notation for a complete graph is Kn, can we say that every complete graph where n > 4 is non planar?
Yeah. Since every Kn graph where n > 5 has a K5 subgraph.
That was amazing...
Made my concept crystal clear...
Thanx a lot :)
Thanks, man! This video helped me a lot!
Amazing video..Really helped a lot. Thank you!!
what does crossing of edges mean? Do they cross only in 2d or can the graph be visualized in 3d as well?
These graphs exist on a 2D plane.
ok.. thanks!
planar graphs are a bit confusing..
What about this criteria: For every planar Graph G = (V, E) wtih |V | = n, |E| = m ≥ 3:
m ≤ 3n − 6
and
For every planar Graph G= (V, E) with |V | = n, |E| = m ≥ 3 and
without cycles of length 3: m ≤ 2n − 4
Does this work or are there problems?
Helps me a lot, thanks!
Thanks for your nice lectures. May I know is an empty graph (a graph with no edges) a planner graph? How about graph G that is the union of an isolated vertex and a complete graph of order 2, is G planner? Thank you
(1) Yes, by definition, an empty graph is planar. (2) What do you mean by a complete graph of order 2? If you are referring to a complete graph with 2 vertices (which is essentially an edge), then yes, it is planar.
u saved my life bro... great vid !!! :)
Great explanation man!
Thanks for the help! God bless you
is it possible to draw the edges of the graph in such a way that the edges do not cross?
Your video is very helpful! Thank you very much!
Had a question...when we subdivide a graph can the degree of a vertex change?
When you subdivide a graph, the degree of a vertex may change. Subdividing a graph involves replacing an edge with a new vertex and two new edges. The new vertex is inserted along the original edge, splitting it into two separate edges.
You are awesome!!!!!
i was looking for a demoucron malgrange pertuiset algorithm video. writing it out and searching gave me nothing. any luck finding it on youtube?
btw ur videos helped me out a lot in the past and for that i thank u
You are so good to explain. Thank you!
This is so hard to understand I tried to look up a level maths and this came up I'm so baffled now
Hey Trev, it's homeomorphic, not homomorphic. Graph homomorphism is very different from homeomorphism.
You prove non-planarity by showing that it has a subgraph that is a subdivision of k5 or k3,3, but how do you prove planarity then?
by drawing the graph in such a way that it is flat and no edges cross.
Is forest a planar graph ?
9:41 I thought you said planar has no crossing edges? What sorcery is this?
"Planar" means "can be drawed as a plane graph". A plane graph has no crossing edges
kura toes key?
Hello Trev! The homomorphism concept u explained in the beginning does not seem correct to me when I compare it to the one explained here: th-cam.com/video/RatkBWHUSqo/w-d-xo.html . Are you sure that H is homomorphic to G?? Can't find a proper vertex maping function!!
I can't do it.
therefore, it's not planar. □
can i not siply use the formula m>=3n-6?(eulers formula)
我意识到了学英语的重要性
6:18 Ayo?
Dude you can just use Euler's formula to count the vertices and edges ... It's more like proving you don't even need to draw
Euler's forumla is only good for checking if the current drawing of the graph is planar or not. It won't tell you if there is a different drawing of the graph that is planar which is the hard part.