Скачать с ютуб Degree Sequence of a Graph | Graph Theory, Graphical Sequences в хорошем качестве

Degree Sequence of a Graph | Graph Theory, Graphical Sequences

What is a degree sequence of a graph? Are graphs with the same degree sequence isomorphic? Do isomorphic graphs have the same degree sequence? We’ll go over all of this in today’s video graph theory lesson! Recall that the degree of a vertex is the number of edges incident to the vertex. If we list the vertex degrees of a graph in a sequence, that sequence is called a degree sequence. By some definitions, a degree sequence has to be non-increasing, meaning each degree in the sequence is greater than or equal to the next degree. The nice thing about that definition is it makes the degree sequence of each graph unique, so there is only one degree sequence for each graph! As I always say, be aware of the definition being used since there are multiple in use for this term. It is clear that if two graphs are isomorphic, they must have the same degree sequences. We do not prove this in the lesson but we do look at a small example of it. The converse is more interesting and not true. If two graphs have the same degree sequences they are not necessarily isomorphic, and we will see an interesting example of that! Of course it is clear that every graph has at least one degree sequence, but is every finite sequence of nonnegative integers the degree sequence of some graph? If a sequence is a degree sequence of some graph, we call it graphical. So is every finite sequence of nonnegative integers graphical? What do you think? Watch the full video lesson for more! Here is an example of a finite sequence of nonnegative integers that is not graphical: 1, 0. Such a graph would need to have two vertices, call them x and y. Suppose x has degree 1, then it must be adjacent to y, which means both x and y have degree 1. Clearly, no graph exists with two vertices, one of degree 1, and the other degree 0. More generally, if a sequence of length n has a 0 in it, and it has n-1 in it, then it cannot be graphical. Because if a graph has n vertices and a vertex has degree n-1, that means it is adjacent to every other vertex in the graph, so every other vertex must have degree at least 1. Thus, there cannot be a degree of 0 in such a graph. If you're taking a course in Graph Theory, or preparing to, you may be interested in the textbook that introduced me to Graph Theory: “A First Course in Graph Theory“ by Gary Chartrand and Ping Zhang. It’s a wonderful text! You can purchase this book through my Amazon affiliate link below! Using the affiliate link costs you nothing extra, and helps me continue to work on Wrath of Math! PURCHASE "A First Course in Graph Theory": https://amzn.to/31hgvvJ I hope you find this video helpful, and be sure to ask any questions down in the comments! ******************************************************************** The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work. Vallow Bandcamp: https://vallow.bandcamp.com/ Vallow Spotify: https://open.spotify.com/artist/0fRtu... Vallow SoundCloud:   / benwatts-3   ******************************************************************** +WRATH OF MATH+ ◆ Support Wrath of Math on Patreon:   / wrathofmathlessons   Follow Wrath of Math on... ● Instagram:   / wrathofmathedu   ● Facebook:   / wrathofmath   ● Twitter:   / wrathofmathedu   My Music Channel:    / seanemusic