Subgraphs

Graph Theory · Axiom Academy

Understanding how graphs contain smaller graphs within them In simpler terms, a subgraph is formed by selecting some vertices and some edges from the original graph. The selected edges must connect only the selected vertices. Watch the animation to see how a subgraph is extracted from a parent graph: An induced subgraph is determined entirely by choosing vertices. Once you select the vertices, you must include all edges between those vertices that exist in the parent graph. The animation shows how selecting vertices automatically determines the induced subgraph: In a spanning subgraph, we keep all the vertices but may remove some edges. This is useful in many applications, such as finding spanning trees or network design. Watch how we create spanning subgraphs by keeping all vertices but selecting different edge sets: Spanning Tree: A spanning subgraph that is a tree (connected and acyclic) Spanning Forest: A spanning subgraph where each component is a tree Matchings: Spanning subgraphs where each vertex has degree at most 1 A proper subgraph is strictly smaller than the parent graph in some way. Every graph is a subgraph of itself, but not a proper subgraph of itself. The animation demonstrates various proper subgraphs of the same parent graph: This is the dual concept to vertex-induced subgraphs. You select edges first, and the necessary vertices are automatically included. Watch how selecting edges determines the edge-induced subgraph: Finding paths and cycles in graphs

This is the written version of the interactive lesson above. See the full Graph Theory course.