# Subgraph

A Subgraph is a subset of the graph nodes and graph edges of a graph.

**AKA:**Graph Cluster.**Context:**- It can range from being a Connected Subgraph to being an Unconnected Subgraph.
- It can range from being a Subgraph Dataset to being a Formal Subgraph.
- It can range from being a Dense Subgraph to being a Sparse Subgraph.
- It can be found by a Subgraph Finding System (that solves a subgraph finding task).
- It can be a Common Subgraph.

**Example(s):**- a Clique.
- a Subtree.
- a Graph Edge Sequence.
- …

**Counter-Example(s):**- a Graph Set.

**See:**Substructure, Proper Subgraph.

## References

### 2013

- http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Subgraphs
- A
**subgraph**of a graph*G*is a graph whose vertex set is a subset of that of*G*, and whose adjacency relation is a subset of that of*G*restricted to this subset. In the other direction, a supergraph of a graph*G*is a graph of which*G*is a subgraph. We say a graph*G***contains**another graph*H*if some subgraph of*G*is*H*or is isomorphic to*H*.A subgraph

*H*is a**spanning subgraph**, or**factor**, of a graph*G*if it has the same vertex set as*G*. We say*H*spans*G*.A subgraph

*H*of a graph*G*is said to be induced (or**full**) if, for any pair of vertices*x*and*y*of H,*xy*is an edge of*H*if and only if*xy*is an edge of G. In other words,*H*is an induced subgraph of*G*if it has exactly the edges that appear in*G*over the same vertex set. If the vertex set of*H*is the subset*S*of*V(G)*, then*H*can be written as*G*[*S*] and is said to be induced by*S*.A graph that does not

*contain*H*as an induced subgraph is said to be*.*H*-free^{[citation needed]}*A***universal graph**in a classof graphs is a simple graph in which every element in*K*can be embedded as a subgraph.*K**A graph**G*is minimal with some property*P*provided that*G*has property*P*and no proper subgraph of*G*has property*P*. In this definition, the term*subgraph*is usually understood to mean "induced subgraph." The notion of maximality is defined dually:*G*is**maximal**with*P*provided that*P*(*G*) and*G*has no proper supergraph*H*such that*P*(*H*).

- A

### 2009

- http://en.wiktionary.org/wiki/subgraph
- A section of a graph or network

- http://www2.parc.com/istl/groups/hdi/sensemaking/glossary.htm
- A connected subset of a graph. Typically, a subgraph is a connected subset of nodes and links from a larger graph. ...