What is a Vertex Induced Subgraph? | Graph Theory

What are vertex-induced subgraphs? We go over them in today's math lesson! Recall that a graph H is a subgraph of a graph G if and only if every vertex in H is also in G, and every edge in H is also in G. In other words, the vertex set and edge set of H are subsets of the vertex set and edge set of G, respectively. Then, H is a vertex-induced subgraph of G if and only if every pair of vertices in H, that is joined by an edge in G, is also joined by an edge in H. So two vertices in H are adjacent if and only if they are adjacent in G, this is what makes a subgraph a vertex-induced subgraph. We can think of it as taking some vertices from G, and all edges joining any of those vertices.

Suppose G = ( { a, b, c, d, e }, { ab, ac, de, da, ce, db } ). We can denote the subgraph of G induced by the vertex set A as G[A]. Let A = { a, c, d }. Then G[A] = ( { a, c, d }, { ac, da } ). The graph G[A] is a vertex-induced subgraph of G, and it is induced by the vertex set A. So G[A] has all vertices in A, and has all edges from G that join any vertices in A.

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 Soundcloud: 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  

Music Channel:    / seanemusic