from Wikipedia, the free encyclopedia

The term subgraph in describing graph theory a relationship between two graphs . Another word for subgraph is subgraph . A graph is a subgraph of the graph if all nodes and edges of are also included in . In other words: A subgraph is created from a graph by removing some nodes and edges from . When removing a node, all incident edges must also be removed.


A graph is called a subgraph or subgraph or subgraph of if its node set is a subset of and its edge set is a subset of , i.e. and holds.

The reverse is then called supergraph or upper graph of .

These terms are not uniform. In the below text book by Klaus Wagner , only the term in this general subgraph used, and a sub-graph defined as a subgraph, which additionally has the property that each edge of the two nodes from connecting also an edge in is. In Claude Berge's textbook , subgraph also means that is, and subgraph means that and every edge out that connects two nodes in is also an edge in , the general case is then called part-subgraph there . It is therefore advisable to check the definition used with each author.

In the case of a node-weighted or edge-weighted graph , it is also required of a subgraph that the weight function of must be compatible with the weight function of , i. H. for each node is valid and for each edge is considered .

If it is also true for a subgraph that all edges between the nodes in contains that are also present in, then one denotes the subgraph of induced by and also notes this down . An induced subgraph is therefore always uniquely determined by the supergraph and the selected node set. For a node-set is denoted by the induced subgraphs consisting by omitting the node is created and their incident node edges, ie .

A subgraph of that contains all nodes of its supergraph is called a spanning subgraph or factor .


In the following figure, the graphs , and subgraphs of , but only and are induced subgraphs. arises from by omitting the nodes and their incident edges, so is . At the same time there is also an induced subgraph of .

Examples of subgraph relationships

See also


Individual evidence

  1. Klaus Wagner: Theory of Graphs , BI University Pocket Books (1969), Volume 248, Chap. I, §3, definition 4
  2. Claude Berge: Programs, games, transport networks , Teubner-Verlag 1969, part of the time, chap. I, paragraph 1, page 121