Good spanning tree

<p>In the <a href="/facts/Mathematics/pxTouaz4">mathematical</a> field of <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, a good spanning tree  
  
    
      
        T
      
    
    {\displaystyle T}
  
 of an <a href="/facts/Planar_graph/plREagr9">embedded planar graph</a> 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is a rooted <a href="/facts/Spanning_tree/qQPN9taR">spanning tree</a> of <i>
  
    
      
        G
      
    
    {\displaystyle G}
  
</i>  whose non-tree edges satisfy the following conditions.
</p>
<ul><li>there is no non-tree edge 
  
    
      
        (
        u
        ,
        v
        )
      
    
    {\displaystyle (u,v)}
  
 where 
  
    
      
        u
      
    
    {\displaystyle u}
  
 and 
  
    
      
        v
      
    
    {\displaystyle v}
  
 lie on a path from the root of 
  
    
      
        T
      
    
    {\displaystyle T}
  
  to a leaf,</li>
<li>the edges incident to a vertex 
  
    
      
        v
      
    
    {\displaystyle v}
  
 can be divided by three sets 
  
    
      
        
          X
          
            v
          
        
        ,
        
          Y
          
            v
          
        
      
    
    {\displaystyle X_{v},Y_{v}}
  
 and 
  
    
      
        
          Z
          
            v
          
        
      
    
    {\displaystyle Z_{v}}
  
, where,
<ul><li>
  
    
      
        
          X
          
            v
          
        
      
    
    {\displaystyle X_{v}}
  
 is a set of non-tree edges, they terminate in red zone</li>
<li>
  
    
      
        
          Y
          
            v
          
        
      
    
    {\displaystyle Y_{v}}
  
 is a set of tree edges, they are children of 
  
    
      
        v
      
    
    {\displaystyle v}
  
</li>
<li>
  
    
      
        
          Z
          
            v
          
        
      
    
    {\displaystyle Z_{v}}
  
 is a set of  non-tree edges, they terminate in green zone</li></ul></li></ul>

Good spanning tree open-in-new

Good spanning tree