isomorphic subgraph with tree $T$

96 Views Asked by At

Let $T$ be a tree with $k$ edges. Proof that each graph $G$, where $$ \forall_v \text{ } deg(v) \ge k $$ contains isomorphic subgraph with tree $T$

My idea

If $ \forall_v \text{ } deg(v) \ge k $ then in $G$ is a path $P$ with $k$ vertices so we can choose random path from tree and it will be equivalent to our $P$. If each vertex contains $k$ neighbors so next elements from graph can be connected to $P$.

1

There are 1 best solutions below

0
On BEST ANSWER

Every tree can be "produced" in the following way: start with the root, and repeatedly attach vertices to existing vertices. For example, a path of length $k$ can be generated by starting with $v_0$, attaching $v_1$ to $v_0$, then $v_2$ to $v_1$, and so on, until $v_k$ to $v_{k-1}$; and a $k$-star can be generated starting with $v_0$ and attaching $v_1,\ldots,v_k$ to $v_0$.

Given this kind of recipe for $T$, we can embed it into $G$ vertex by vertex. Embed the root $r$ of $T$ at an arbitrary vertex $\phi(r)$ of $G$. When attaching the new vertex $y$ to an existing vertex $x$, find a neighbor $\phi(y)$ of $\phi(x)$ which is different than all nodes which are already mapped to in $G$. At each point in time, there are at most $k-1$ forbidden nodes, so we can always find such a neighbor.