Induced subgraph

<h2 id="definition">Definition</h2>
<p>Formally, let 
  
    
      
        G
        =
        (
        V
        ,
        E
        )
      
    
    {\displaystyle G=(V,E)}
  
 be any graph, and let 
  
    
      
        S
        ⊆
        V
      
    
    {\displaystyle S\subseteq V}
  
 be any subset of vertices of G. Then the induced subgraph 
  
    
      
        G
        [
        S
        ]
      
    
    {\displaystyle G[S]}
  
 is the graph whose vertex set is 
  
    
      
        S
      
    
    {\displaystyle S}
  
 and whose edge set consists of all of the edges in 
  
    
      
        E
      
    
    {\displaystyle E}
  
 that have both endpoints in 
  
    
      
        S
      
    
    {\displaystyle S}
  
.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a> That is, for any two vertices 
  
    
      
        u
        ,
        v
        ∈
        S
      
    
    {\displaystyle u,v\in S}
  
, 
  
    
      
        u
      
    
    {\displaystyle u}
  
 and 
  
    
      
        v
      
    
    {\displaystyle v}
  
 are adjacent in 
  
    
      
        G
        [
        S
        ]
      
    
    {\displaystyle G[S]}
  
 if and only if they are adjacent in 
  
    
      
        G
      
    
    {\displaystyle G}
  
. The same definition works for <a href="/facts/Undirected_graph/kw3eIBUe">undirected graphs</a>, <a href="/facts/Directed_graph/YBdfQ0um">directed graphs</a>, and even <a href="/facts/Multigraph/udmS0Cp0">multigraphs</a>.
</p><p>The induced subgraph 
  
    
      
        G
        [
        S
        ]
      
    
    {\displaystyle G[S]}
  
 may also be called the subgraph induced in 
  
    
      
        G
      
    
    {\displaystyle G}
  
 by 
  
    
      
        S
      
    
    {\displaystyle S}
  
, or (if context makes the choice of 
  
    
      
        G
      
    
    {\displaystyle G}
  
 unambiguous) the induced subgraph of 
  
    
      
        S
      
    
    {\displaystyle S}
  
.
</p>
<h2 id="examples">Examples</h2>
<p>Important types of induced subgraphs include the following.
</p>

<ul><li><a href="/facts/Induced_path/zfcIx9Sw">Induced paths</a> are induced subgraphs that are <a href="/facts/Path_(graph_theory)/WMsq21Nf">paths</a>. The <a href="/facts/Shortest_path/g4nsrswr">shortest path</a> 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 <a href="/facts/Distance-hereditary_graph/T17SFUmL">distance-hereditary graphs</a>, every induced path is a shortest path.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a></li>
<li><a href="/facts/Induced_cycle/zfcIx9Sw">Induced cycles</a> are induced subgraphs that are <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycles</a>. The <a href="/facts/Girth_(graph_theory)/rPwRGgxj">girth</a> of a graph is defined by the length of its shortest cycle, which is always an induced cycle. According to the <a href="/facts/Strong_perfect_graph_theorem/XcIR3USE">strong perfect graph theorem</a>, induced cycles and their <a href="/facts/Complement_graph/IdHUPFr3">complements</a> play a critical role in the characterization of <a href="/facts/Perfect_graph/wcPdhjG9">perfect graphs</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a></li>
<li><a href="/facts/Clique_(graph_theory)/XK9ppLz5">Cliques</a> and <a href="/facts/Independent_set_(graph_theory)/ksu46kdz">independent sets</a> are induced subgraphs that are respectively <a href="/facts/Complete_graph/AYD6hUqI">complete graphs</a> or <a href="/facts/Edgeless_graph/Ro1YV0g6">edgeless graphs</a>.</li>
<li><a href="/facts/Induced_matching/3lxYGGK6">Induced matchings</a> are induced subgraphs that are <a href="/facts/Matching_(graph_theory)/s0pUJ7hd">matchings</a>.</li>
<li>The <a href="/facts/Neighbourhood_(graph_theory)/E6V1hk6b">neighborhood</a> of a vertex is the induced subgraph of all vertices adjacent to it.</li></ul>
<h2 id="computation">Computation</h2>
<p>The <a href="/facts/Induced_subgraph_isomorphism_problem/XBKgfULs">induced subgraph isomorphism problem</a> is a form of the <a href="/facts/Subgraph_isomorphism_problem/86LLWRg4">subgraph isomorphism problem</a> in which the goal is to test whether one graph can be found as an induced subgraph of another. Because it includes the <a href="/facts/Clique_problem/cVVBNP08">clique problem</a> as a special case, it is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Diestel, Reinhard (2006), Graph Theory, Graduate texts in mathematics, vol. 173, Springer-Verlag, pp. 3–4, ISBN 9783540261834. <a href="9783540261834" target="_blank">9783540261834</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Howorka, Edward (1977), "A characterization of distance-hereditary graphs", The Quarterly Journal of Mathematics, Second Series, 28 (112): 417–420, doi:10.1093/qmath/28.4.417, MR 0485544. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem", Annals of Mathematics, 164 (1): 51–229, arXiv:math/0212070, doi:10.4007/annals.2006.164.51, MR 2233847. <a href="/wiki/Maria_Chudnovsky" target="_blank">/wiki/Maria_Chudnovsky</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Johnson, David S. (1985), "The NP-completeness column: an ongoing guide", Journal of Algorithms, 6 (3): 434–451, doi:10.1016/0196-6774(85)90012-4, MR 0800733. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

Induced subgraph open-in-new

Induced subgraph