What is the K-Core of a Graph? | K-Cores, Degeneracy, Graph Theory

What is the k-core of a graph? Yes I said THE k-core. For a given value of k (which can be any integer), the k-core of a graph is unique, at least with the definition we are using! We define k-cores, and go over examples in today's graph theory video lesson!

The k-core of a graph G is the maximal subgraph H such that the minimum degree of H is at least k. Thus, ever vertex in a k-core must have degree at least k. A k-core does not need to be connected by this definition, however some authors will require that k-cores be connected, which removes their property of uniqueness.

In today's lesson we take a look at a graph's 0-core, 1-core, 2-core, 3-core, and 4-core, and we go over the process of finding them all! To find the k-core of a graph, we just need to repeatedly delete vertices with degree less than k until no such vertices remain! Sometimes nothing will remain, and we see that in this video!

The 0-core of any graph is the graph itself, because no vertex has degree less than 0.

What are cliques:    • What is a Clique? | Graph Theory, Cli...  
What is a k-Clique:    • What are k-Cliques? | Graph Theory  
What are k-clans and k-Clubs:    • What are k-Cliques? | Graph Theory  
What is a k-Plex:    • What is a k-Plex? | Graph Theory  

You can read more about k-cores in the following paper, which is where I got the graph used in the video, as I thought it made an excellent example.

The k-Cores of a Graph by Allan Bickle: https://scholarworks.wmich.edu/cgi/vi...

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