Forbidden subgraph problem

<p>In <a href="/facts/Extremal_graph_theory/mdkBX6yN">extremal graph theory</a>, the forbidden subgraph problem is the following problem: given a graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
, find the maximal number of edges 
  
    
      
        ex
        ⁡
        (
        n
        ,
        G
        )
      
    
    {\displaystyle \operatorname {ex} (n,G)}
  
 an 
  
    
      
        n
      
    
    {\displaystyle n}
  
-vertex graph can have such that it does not have a <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraph</a> <a href="/facts/Graph_isomorphism/SBjVIhwW">isomorphic</a> to 
  
    
      
        G
      
    
    {\displaystyle G}
  
. In this context, 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is called a forbidden subgraph.
</p><p>An equivalent problem is how many edges in an 
  
    
      
        n
      
    
    {\displaystyle n}
  
-vertex graph guarantee that it has a subgraph isomorphic to 
  
    
      
        G
      
    
    {\displaystyle G}
  
?
</p>

Forbidden subgraph problem open-in-new

Forbidden subgraph problem