# How to fill in the gaps in my proof to make it more convincing?

Let $T$ be a tree with $3$ edges. Let $G$ be a simple graph such that each vertex has degree at least $3$. Show that $G$ has $T$ as a subgraph.

This statement is obvious but I am not sure how to prove it rigorously.

Could anybody please help me check whether my proof is good enough or not, and some advice for improvement if possible. I really think my proof is not good enough, because I am not sure how to fill in the details to make the proof more convincing. Thanks!

Since $T$ is a tree with $3$ edges, then each vertex of $T$ has at least $1$ edge and at most $3$ edges. Then we can extend $T$ by adding edges and vertices so that it becomes $G$, it possible because $G$ has degree at least $3$.

EDITED

We can find a vertex in $T$ that has degree less than $3$, then we can connect that vertex with an edge to another vertex that has degree less than $3$. But we have to make sure there is no loop created. We can keep adding edges so that all vertices have at least $3$ edges. But $G$ is given, so we have to add all the edges according to $G$.

My other concerns are (out of curiosity): as the number of edges increases to a general $n$ edges, then we need to deal with each case of possible graphs with $n$ edges, is there a better way besides dealing with each possible shape of the tree?

Let's say $T$ has 5 edges, then there are more than two trees that has 5 edges, does that mean we have to deal with each case and extend the tree from each case? Is there any better way?

• There are only two trees with three edges. Can you show that $G$ must contain one or the other? – Ethan Bolker May 19 '16 at 12:36
• @EthanBolker I can do it by drawing, but not sure how to put into words? It is quite intuitive that $G$ must contain either one of them. – user338393 May 19 '16 at 12:40
• @user338393 Better to start with what you know that what you want. Here you know that $G$ has a vertex with degree at least 3. How does that help? – almagest May 19 '16 at 12:41
• @almagest that means we can add more edges and vertices to $T$ so that all vertices have degree at least 3? – user338393 May 19 '16 at 12:44
• Start from the vertex. Not from $T$. You have a vertex with three others joined to it. So you have dealt with one possible $T$. Now what about the other? – almagest May 19 '16 at 12:45

There are essentially two different trees with $3$ edges. You can have all three edges incident at the same vertex; this is the star graph $S_3$. Or you can have at most $2$ edges incident at any vertex – then the tree is the path graph $P_4$ (why?).
$S_3$ is easy. The claim isn't quite right since it doesn't hold for the empty graph; but if we assume that $G$ is not empty, then it has at least one vertex of degree at least $3$, and any three edges incident at that vertex induce a subgraph isomorphic to $S_3$.
$P_4$ requires a bit more work – I'll leave that to you...
• Thanks. I am still not quite sure even though you say $S_3$ is easy. The problem is $G$ is given, so we have to add the vertices and edges carefully. Is there another way to show a graph is a subgraph of another graph? I have made an edit to my post, could you please give some advice on the edit and how can I improve it? – user338393 May 19 '16 at 13:01
• @user338393: This idea of adding edges to $T$ to create all of $G$ seems misguided to me. You just have to exhibit the subgraph; that any remaining edges can be added to a subgraph of $G$ to obtain $G$ is trivial. The work in this proof lies in proving that $G$ contains $P_4$ as a subgraph. For $S_3$, there's nothing left to do -- every vertex has $3$ edges, and that vertex, those three edges and their three other endpoints together form a subgraph of $G$ isomorophic to $S_3$. – joriki May 19 '16 at 13:09