Home /
Expert Answers /
Advanced Math /
please-help-spanning-subgraphs-a-spanning-subgraph-of-a-graph-g-is-a-subgraph-obtained-pa528

Please help

SPANNING SUBGRAPHS A spanning subgraph of a graph \( G \) is a subgraph obtained by edge deletions or in other words, a subgraph whose vertex set is the entire vertex set of \( G \). If \( s \) the set of deleted edges, this subgraph of \( G \) is denoted \( G \backslash S \). Observe that ev simple graph is a spanning subgraph of a complete graph. Spanning supergraphs are defined analogously. The inverse operation to e deletion is edge addition. Adding a set \( S \) of edges to a graph \( G \) yields a spann supergraph of \( G \), denoted \( G+S \). By starting with a disjoint union of two graj \( G \) and \( H \) and adding edges joining every vertex of \( G \) to every vertex of \( H \), obtains the join of \( G \) and \( H \), denoted \( G \vee H \). The join \( C_{n} \vee K_{1} \) of a cycle \( C_{n} \) an single vertex is referred to as a wheel with \( n \) spokes and denoted \( W_{n} \). (The gra 2.2 Spanning and Induced Subgraphs (a) (b) Fig. 2.3. (a) A graph and (b) its underlying simple graph \( H \) of Figure \( 1.1 \) is the wheel \( W_{5} \).) One may also add a set \( X \) of vertices to a graa resulting in a supergraph of \( G \) denoted \( G+X \). Certain types of spanning subgraph occur frequently in applications of gra theory and, for historical reasons, have acquired special names. For example, sp ning paths and cycles are called Hamilton paths and Hamilton cycles, respectiv and spanning \( k \)-regular subgraphs are referred to as \( k \)-factors. Rédei's Theor (Theorem 2.3, see inset) tells us that every tournament has a directed Hamil path. Not every tournament (on three or more vertices) has a directed Hamil cycle, however; for instance, the transitive tournament has no directed cycles all. Nonetheless, Camion (1959) proved that every tournament in which any tex can be reached from any other vertex by means of a directed path does inde have a directed Hamilton cycle (Exercise 3.4.12a). By deleting from a graph \( G \) all loops and, for every pair of adjacent vertices, but one link joining them, we obtain a simple spanning subgraph called the und lying simple graph of \( G \). Up to isomorphism, each graph has a unique underly simple graph. Figure \( 2.3 \) shows a graph and its underlying simple graph. Given spanning subgraphs \( F_{1}=\left(V, E_{1}\right) \) and \( F_{2}=\left(V, E_{2}\right) \) of a graph \( G \) \( (V, E) \), we may form the spanning subgraph of \( G \) whose edge set is the symmet difference \( E_{1} \triangle E_{2} \) of \( E_{1} \) and \( E_{2} \). This graph is called the symmetric difference \( F_{1} \) and \( F_{2} \), and denoted \( F_{1} \Delta F_{2} \). Figure \( 2.4 \) shows the symmetric difference of spanning subgraphs of a graph on five vertices. Fig. 2.4. The symmetric difference of two graphs
assume that \( v(F)>1 \). Suppose, by way of contradiction, that \( d_{F}(v) \leq k \) for some vertex \( v \) Consider the vertex-deleted subgraph \( F^{\prime}:=F-v \). Note that \( F^{\prime} \) is also an in subgraph of \( G \). Moreover \[ d\left(F^{\prime}\right)=\frac{2 e\left(F^{\prime}\right)}{v\left(F^{\prime}\right)} \geq \frac{2(e(F)-k)}{v(F)-1} \geq \frac{2 e(F)-d(G)}{v(F)-1} \geq \frac{2 e(F)-d(F)}{v(F)-1}=d(F \] Because \( v\left(F^{\prime}\right)

Theorem 5.10 :) Every connected graph without cut edges has a strong orientation. Proposition 5.9 will be used to prove the given theorem 5.10 which s