dude why does this make so much sense when the textbook reads like I found a mandarin translation to create the Philosopher's Stone? ( For those that can read both English and Mandarin, sub in cuneiform or some equally difficult language to read)
Question!! At 17:38 how come the +(2l) is part of the equation? what does degree remaining imply? I was able to do the same proof without that term because everything still works the same. I am just uncertain what that term represents? The first term (2k+1) is an odd number of vertices and the second term (2j+1) is the odd degree so I do not get what I'm missing. Thank you in advance!
Because the no. of vertices (which are odd 1,3,5 etc) x degree of odd vertices gives the total degrees from odd vertices. But he's assumed that all vertices have an odd degree which they don't because in an odd number of vertices there is both odd and even degree vertices. Then he goes on to add the number of degrees from the even vertices, the equation is just wrong
In a graph, there can be both even and odd degree vertices. He assumes that there are odd number of odd degree vertices which you understood. There might also be even degree vertices which the 2*l represents.
His equation is not rigorous. Suppose: n: be the number of all vertices 2m + 1: be odd vertices number n - (2m + 1): the remaining (even) vertices So, now we will divide the degrees into two categories, even and odd. Since we want to proof by contradiction, then we want to show that a graph can have an odd number of odd-degree vertices. Given the equation: sum( deg(Vi) ) = 2 |E| such that i: vertex degree from 1 to n We can rewrite it as: sum( deg(Vi) ) + sum( deg(Vj) ) = 2 |E| such that Vi: is the ith vertex odd-degree, i: from 1 to (2m+1) and Vj: is the jth vertex even-degree, j: from 1 to (n - (2m + 1)) From the original equation, we know that the left-hand side of the equation should evaluate to even. Since the sum( deg(Vi) ) is odd (since the sum of odd value (2m + 1) time evaluates to an odd value ), then sum( deg(Vj) ) has to be odd as well because odd + odd will evaluate to even which is not the case, because the second summation is the sum of even values which evaluates to even, hence the LHS = odd + even = odd which contradict with the RHS = even, hence a proof by contradiction that a graph cannot has an odd number of odd-degree vertices.
Thank You for the discrete mathematics playlist. It's so damn helpful! I love it! Do you have a video which covers vertices degrees of directed graphs??
Thank you for this wonderful videos . With your knowledge of Discrete Mathematics am sure you know so much about Database Management System or Networking. If you do, please also make some videos teaching them . I left Maths like almost 14 years after ago and your channels has really been helpful to me since last 2018.
Consider an undirected graph G that has n distinct vertices where each vertex has degree 2. Assume n≥3. What is the maximum number of circuits that G can contain? If all the vertices of G are contained in a single circuit, what is the maximum number of vertices that can be contained in an independent set?
![[Discrete Mathematics] Euler Circuits and Euler Trails](http://i.ytimg.com/vi/Ou345pSYDoE/mqdefault.jpg)
![[Discrete Mathematics] Euler Circuits and Euler Trails](/img/tr.png)
you are an angel for a computer science student
😂
agreed
on around 15:50 , you assume that the odd degree vertices have the same value, which is not the case.
dude why does this make so much sense when the textbook reads like I found a mandarin translation to create the Philosopher's Stone? ( For those that can read both English and Mandarin, sub in cuneiform or some equally difficult language to read)
My textbook about Fundamentals of Computer Science has so many weird terms, I feel like I'm summoning a demon when I'm reading it lmao
Question!! At 17:38 how come the +(2l) is part of the equation? what does degree remaining imply? I was able to do the same proof without that term because everything still works the same. I am just uncertain what that term represents? The first term (2k+1) is an odd number of vertices and the second term (2j+1) is the odd degree so I do not get what I'm missing. Thank you in advance!
His mathematics for that question is just wrong
Because the no. of vertices (which are odd 1,3,5 etc) x degree of odd vertices gives the total degrees from odd vertices. But he's assumed that all vertices have an odd degree which they don't because in an odd number of vertices there is both odd and even degree vertices. Then he goes on to add the number of degrees from the even vertices, the equation is just wrong
In a graph, there can be both even and odd degree vertices. He assumes that there are odd number of odd degree vertices which you understood. There might also be even degree vertices which the 2*l represents.
@@MichaelLee-sb3du I was also confused at first but I watched another video and then I understood.
His equation is not rigorous.
Suppose:
n: be the number of all vertices
2m + 1: be odd vertices number
n - (2m + 1): the remaining (even) vertices
So, now we will divide the degrees into two categories, even and odd. Since we want to proof by contradiction, then we want to show that a graph can have an odd number of odd-degree vertices.
Given the equation: sum( deg(Vi) ) = 2 |E|
such that i: vertex degree from 1 to n
We can rewrite it as: sum( deg(Vi) ) + sum( deg(Vj) ) = 2 |E|
such that Vi: is the ith vertex odd-degree, i: from 1 to (2m+1)
and Vj: is the jth vertex even-degree, j: from 1 to (n - (2m + 1))
From the original equation, we know that the left-hand side of the equation should evaluate to even. Since the sum( deg(Vi) ) is odd (since the sum of odd value (2m + 1) time evaluates to an odd value ), then sum( deg(Vj) ) has to be odd as well because odd + odd will evaluate to even which is not the case, because the second summation is the sum of even values which evaluates to even, hence the LHS = odd + even = odd which contradict with the RHS = even, hence a proof by contradiction that a graph cannot has an odd number of odd-degree vertices.
Thank you, your explanation is very clear and easy to understand
Thank You for the discrete mathematics playlist. It's so damn helpful! I love it!
Do you have a video which covers vertices degrees of directed graphs??
Bro you are a saviour thanks so much
thank you so much brother, this is one hell of a help
EXCELLENT JOB.
Thank you for this wonderful videos .
With your knowledge of Discrete Mathematics am sure you know so much about Database Management System or Networking.
If you do, please also make some videos teaching them .
I left Maths like almost 14 years after ago and your channels has really been helpful to me since last 2018.
Did you fail to mention that it is called handshake theorem or have you mentioned it somewhere else?
@14:30 ya'll
Consider an undirected graph G that has n distinct vertices where each vertex has degree 2. Assume n≥3. What is the maximum number of circuits that G can contain? If all the vertices of G are contained in a single circuit, what is the maximum number of vertices that can be contained in an independent set?
Can u please mention the video number which helps us to see full chapter one after the other ?
In the part about hypercubes, I think that you accidentally added one to each binary number; it's actually 0 through 7, not 1 through 8.
What is the degree of a loop in a directed graph? Is it 1? Thanks
maybe InDegree=1 and OutDegree=1? What is the total number of degrees then? Does that question make sense? Thanks
Deg = Sum(id) + Sum(od), so each loop adds 2 degrees overall.
what does odd no. of odd degrees even mean
thank you very helpful
"in a simple graph, must every vertex have degree that is less than the number of vertices in the graph"
5:38 So savage :(
Does deg ^- (v) mean odd
and deg ^+ (v) mean even?
Wish me luck for my "degree" : |
Why tf is my thingy not thingying