Prong Corollary, $G$ has a subgraph isomorphic to $T$

555 Views Asked by At

There is a corollary in Diestel textbook Graph Theory.

Corollary 1.5.4. if $T$ is a tree and $G$ is any graph with $\delta(G) \geq |T|-1$, then $T \subseteq G$, i.e. $G$ has a subgraph isomorphic to $T$.

Proof: Find a copy of $T$ in $G$ inductively along its vertex enumeration from Corollary 1.5.2.

Corollary 1.5.2.The vertices of a tree can always be enumerated, say as $v_1,\dots,v_n$, so that every $v_i$ with $i\geq2$ has a unique neighbor in $\{v_1,\dots,v_{i-1}\}$.

I have some difficulties in approaching the proof. In addition, it looks like Corollary 1.5.2 is very fundamental and very helpful in proving tree poreperties by induction.

I would appreciate any help in proving Corollary 1.5.4.

1

There are 1 best solutions below

0
On

We use induction on $|T|$. Base case is trivially true. Suppose it is true for all trees $T^\prime$ with $|T^\prime| < |T|$.

Consider a terminal vertex (degree $1$ vertex) in the tree $T$. Removing that vertex (say $v$) and the corresponding edge (say $(v,u)$) gives another tree $T^\prime$ with $|T^\prime| <|T|$. And as $\delta(G) \geq |T|-1$ implies $\delta(G) \geq |T^\prime|-1$, by induction assumption, we have $T^\prime \subseteq G$. Let $T_1$ be a subgraph of $G$, isomorphic to $T^\prime$. Let $u_1 \in T_1$ be the vertex corresponding to $u$ (vertex adjacent to the removed vertex) in $T$. As minimum degree of the graph is at least $|T|-1$, there must be at least one vertex that is connected to $u_1$, but is not present in $T_1$. Picking any such vertex and mapping it to $v$ gives a subgraph of $G$ isomorphic to $T$.