What is an Edge-Induced Subgraph? | Graph Theory

What is an edge-induced subgraph? Edge-induced subgraphs are, in my opinion, a less interesting counterpart to vertex-induced subgraphs, but we will go over them in today's math lesson nonetheless!

So just what are edge induced subgraphs? Edge induced subgraphs are basically subgraphs created by taking some edges from a graph, and also taking all vertices incident with those edges. So, if G = ( { a, b, c, d, e }, { ab, ac, de, db } ), then H = ( { a, b, d }, { ab, db } ) is an edge-induced subgraph of G because it is a subgraph of G with no isolated vertices. If a subgraph has no isolated vertices, then it is an edge induced subgraph because it contains some edges, and must contain all vertices incident with those edges.

We have a special notation for edge-induced subgraphs. If S is a set of edges in G, then we say that G[ S ] is the subgraph of G induced by the edge set S. So, for example, G[ {ab, db} ] = ( { a, b, d }, { ab, db } ). See that in G[ { ab, db } ], we include the two edges from the set of edges, and then we just have to also include all incident vertices. Again, we can think of an edge-induced subgraph as being any subgraph that can be created by taking some egdes and then taking all of the vertices incident with those edges.

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