Topics: Graph Theory - Graph


A graph is a subgraph of another graph when:

  • All of the vertices of are contained in .
  • Every edge in has the same terminal vertices in .

Subgraphs can be edge-disjoint or vertex-disjoint.



  • A graph is a subgraph of itself
  • A subgraph of a subgraph of is also a subgraph of (transitivity)
  • A single vertex of is a subgraph
  • An edge with its terminal vertices (in ) is a subgraph of

Edge-Disjoint Subgraphs