In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, an induced subgraph of a graph is another graph, formed from a

subset In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset of ...

of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset.

Definition

Formally, let

G=(V,E)

be any graph, and let

S\subset V

be any subset of vertices of . Then the induced subgraph

G

is the graph whose vertex set is

S

and whose edge set consists of all of the edges in

E

that have both endpoints in

S

. That is, for any two vertices

u,v\in S

u

and

v

are adjacent in

G

if and only if they are adjacent in

G

. The same definition works for

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

s, and even multigraphs. The induced subgraph

G

may also be called the subgraph induced in

G

S

, or (if context makes the choice of

G

unambiguous) the induced subgraph of

S

Examples

Important types of induced subgraphs include the following. Snake in the box

* Induced paths are induced subgraphs that are paths. The

shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between ...

between any two vertices in an unweighted graph is always an induced path, because any additional edges between pairs of vertices that could cause it to be not induced would also cause it to be not shortest. Conversely, in distance-hereditary graphs, every induced path is a shortest path. *

Induced cycle In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edge ...

s are induced subgraphs that are cycles. The

girth Girth may refer to: ;Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...

of a graph is defined by the length of its shortest cycle, which is always an induced cycle. According to the strong perfect graph theorem, induced cycles and their complements play a critical role in the characterization of perfect graphs. * Cliques and independent sets are induced subgraphs that are respectively

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

s or

edgeless graph In the mathematical field of graph theory, the term "null graph" may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph"). Order-zero graph The order-zero graph, , is t ...

s. *

Induced matching In graph theory, an induced matching or strong matching is a subset of the edges of an undirected graph that do not share any vertices (it is a matching) and includes every edge connecting any two vertices in the subset (it is an induced subgraph) ...

s are induced subgraphs that are matchings. *The

neighborhood A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural area, ...

of a vertex is the induced subgraph of all vertices adjacent to it.

Computation

The

induced subgraph isomorphism problem In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph. Problem statement Formally, the problem takes as input two gra ...

is a form of the subgraph isomorphism problem in which the goal is to test whether one graph can be found as an induced subgraph of another. Because it includes the clique problem as a special case, it is

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...

References

{{reflist Graph operations Graph theory objects