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$.


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?

  • $\begingroup$ There are only two trees with three edges. Can you show that $G$ must contain one or the other? $\endgroup$ – Ethan Bolker May 19 '16 at 12:36
  • $\begingroup$ @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. $\endgroup$ – user338393 May 19 '16 at 12:40
  • $\begingroup$ @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? $\endgroup$ – almagest May 19 '16 at 12:41
  • $\begingroup$ @almagest that means we can add more edges and vertices to $T$ so that all vertices have degree at least 3? $\endgroup$ – user338393 May 19 '16 at 12:44
  • $\begingroup$ 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? $\endgroup$ – almagest May 19 '16 at 12:45

You're right, that's not very convincing. :-)

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...

  • $\begingroup$ 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? $\endgroup$ – user338393 May 19 '16 at 13:01
  • 1
    $\begingroup$ @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$. $\endgroup$ – joriki May 19 '16 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.