# Subgraph

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. ${\ displaystyle H}$ ${\ displaystyle G}$ ${\ displaystyle H}$ ${\ displaystyle G}$ ${\ displaystyle H}$ ${\ displaystyle G}$ ${\ displaystyle G}$ ## Definitions

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. ${\ displaystyle G_ {1} = (V_ {1}, E_ {1})}$ ${\ displaystyle G_ {2} = (V_ {2}, E_ {2})}$ ${\ displaystyle V_ {1}}$ ${\ displaystyle V_ {2}}$ ${\ displaystyle E_ {1}}$ ${\ displaystyle E_ {2}}$ ${\ displaystyle V_ {1} \ subseteq V_ {2}}$ ${\ displaystyle E_ {1} \ subseteq E_ {2}}$ The reverse is then called supergraph or upper graph of . ${\ displaystyle G_ {2}}$ ${\ displaystyle G_ {1}}$ 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. ${\ displaystyle G_ {2}}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle V_ {1} = V_ {2}}$ ${\ displaystyle V_ {1} \ subset V_ {2}}$ ${\ displaystyle G_ {2}}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle G_ {1}}$ 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 . ${\ displaystyle G_ {2}}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle g_ {1}}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle g_ {2}}$ ${\ displaystyle G_ {2}}$ ${\ displaystyle v \ in V_ {1}}$ ${\ displaystyle g_ {1} (v) = g_ {2} (v)}$ ${\ displaystyle e \ in E_ {1}}$ ${\ displaystyle g_ {1} (e) = g_ {2} (e)}$ 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 . ${\ displaystyle G_ {1}}$ ${\ displaystyle E_ {1}}$ ${\ displaystyle V_ {1}}$ ${\ displaystyle E_ {2}}$ ${\ displaystyle G_ {1}}$ ${\ displaystyle V_ {1}}$ ${\ displaystyle G_ {2}}$ ${\ displaystyle G_ {2} [V_ {1}]}$ ${\ displaystyle W \ subseteq V}$ ${\ displaystyle G \ setminus W}$ ${\ displaystyle G = (V, E)}$ ${\ displaystyle W}$ ${\ displaystyle G \ setminus W = G [V \ setminus W]}$ A subgraph of that contains all nodes of its supergraph is called a spanning subgraph or factor . ${\ displaystyle G_ {1} = (V, E_ {1})}$ ${\ displaystyle G_ {2} = (V, E_ {2})}$ ## Examples

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 . ${\ displaystyle G_ {1}}$ ${\ displaystyle G_ {2}}$ ${\ displaystyle G_ {3}}$ ${\ displaystyle G}$ ${\ displaystyle G_ {2}}$ ${\ displaystyle G_ {3}}$ ${\ displaystyle G_ {3}}$ ${\ displaystyle G}$ ${\ displaystyle 1,3,7}$ ${\ displaystyle G_ {3} = G \ setminus \ {1,3,7 \}}$ ${\ displaystyle G_ {3}}$ ${\ displaystyle G_ {2}}$ ## 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