Check my proof on showing a graph with each vertex's degree at least $e$ has every tree with $e$ edges a subgraph

Question

Let $T$ be a tree with $e$ edges and $G$ be a simple graph such that ech vertex has degree at least $e$. We need to show that $T$ is a subgraph of $G$.

I tried to prove this by induction.

The base case is trivial.

The induction hypothesis says that for a tree with $e-1$ edges and a simple graph such that each vertex has degree at least $e-1$, then the graph has the tree as a subgraph.

If we add another edge to every single vertex of the graph, then there exists a tree with $e$ edges as a subgraph of the graph since there is already a tree with $e-1$ edges as a subgraph; after we added an edge to every vertex of the graph, the tree with $e$ edges is automatically a subgraph of the graph.

I am not sure whether my proof is correct. If there is something wrong, how could I fix it? Also, is there a better way to improve the writing of the proof?

Thanks.

Answer 1

I disagree with Hagen that you have the right idea. It is a serious logical error you made concerning induction, and I encourage you to read and fully grasp https://matheducators.stackexchange.com/a/10034/1550 before attempting induction problems. After you read that then read my answer.

I give you any tree $T$ and graph $G$ such that every vertex in $G$ has degree at least $e$ where $e$ is the number of edges in $T$. Your task is to show me how to embed $T$ into $G$. How would you do it? To use induction means that you try to reduce your task to a smaller one. What would "smaller task" mean here? That's really up to you, as long as you consistently use the same measure, and you make sure that breaking tasks into smaller one always ends with bits that you can solve directly. One way here would be to use $e$ as the measure of task size, and clearly once $e$ gets down to $0$ you're done. So you notice that if you chop off a leaf from $T$ you get a tree $T'$ with one less edge, and embedding $T'$ into $G$ is a smaller task and hence can be done (by induction). Using the embedding of $T'$ into $G$, can you now see how to embed $T$ into $G$?

Answer 2

You have the right idea, but you should not modify $G$, esp. you cannot expect to obtain a given degree-$e$ graph from an unspecified degree-$(e-1)$ graph. Instead try the following:

Let $T=(V_T,E_T)$ be a tree with $|E_T|=e$ edges (and hence $|V_T|=e+1$ vertices) and let $G=(V_G,E_G)$ be a non-empty, simple graph be given such that all vertices of $G$ have degree $\ge e$. The case $e=0$ is trivial. If $e>0$ then $T$ has at least one leaf $v$. Let $w$ be $v$'s only neighbour. We remove the edge $vw$ and the vertex $v$ from $T$, obtaining a graph $T'=(V_{T'}:=V_T\setminus\{v\}, E_{T'}:=E_T\setminus\{vw\})$ which is a tree with $e-1$ edges (and so $e$ vertices). As in our given $G$, all vertices also have degree $\ge e-1$, we may use the induction hypotheses to embed $T'$ into $G$. That is, there exists an injective map $f\colon V_{T'}\to V_G$ such that $f(x)f(y)\in E_G$ whenever $xy\in E_{T'}$. The vertex $f(w)$ has at least $e$ neighbours. At most $e-1$ of these can be in the image of $f$ (because $|V_{T'}\setminus\{w\}|<e$). Hence let $u$ be a neighbour of $f(w)$ not in the image of $f$. Now define $g\colon V_T\to V_G$ as $$g(x)=\begin{cases}u&\text{if }x=v\\f(x)&\text{otherwise}\end{cases}$$ We verify that $g$ is injective and that $g(x)g(y)\in E_G$ whenever $xy\in E_T$.