Teilgraphs

Teilgraphs, typically referred to in English as subgraphs, are graphs formed from a subset of the vertices and a subset of the edges of a larger graph. If G = (V, E) is a graph, a subgraph H = (V’, E’) consists of V’ ⊆ V and E’ ⊆ E, with the requirement that each edge in E’ joins two vertices in V’.

There are several common subgraph types. An induced subgraph on V’ uses all edges of G whose endpoints lie in V’; that is, E’ contains every edge {u, v} from E with u, v ∈ V’. A spanning subgraph has V’ = V, preserving all vertices but possibly dropping some edges. An edge-induced subgraph is formed by selecting a subset of edges and including all endpoints of those edges, which may introduce new degrees compared to the induced case.

Properties and use: The subgraph relation is transitive and reflexive, and subgraphs can be disconnected. The collection of subgraphs of a fixed graph G forms a natural structure for analyzing local properties, connectivity, and motifs within a larger network. Subgraphs are fundamental in algorithmic graph theory and in the study of graph parameters that are preserved under taking subgraphs.

Computational aspects: The subgraph isomorphism problem asks whether a given graph H occurs as a subgraph of G, a general problem that is NP-complete. Variants arising from induced or bounded-size patterns, or fixed-parameter tractable cases, are studied to identify tractable instances.

Applications: Subgraphs underpin pattern matching, network motif discovery, chemistry (molecular graphs), social network analysis, and various graph-mining tasks where local structure within a larger graph is of interest.