I will preface my question with the definition of a simple tree that applies to my question:

-"A simple tree is an undirected and connected graph with no cycles."-

I am having difficulty coming up with a compelling argument that a tree of the above definition can be constructed by taking a set of disjoint valid graphs and adding a vertex between each of them. The practice problem states:

"Prove that some graph G is a tree if and only if it can be constructed from a set X1, X2, ..., Xi of disjoint valid graphs by adding a new node adjacent to 1 node from each of X1, ..., Xi. A single node is a valid graph."

I'm confused whether this question is asking me to prove that two graphs, or trees ("valid"), can be made into 1 tree by adding a node and adding edges from one preexisting node from each of the trees. If that is how the question should be interpreted, then is it enough to prove that the new tree (or "graph," I guess) has no cycles, and is connected?

I'm new to graph theory and I'm wondering if you geniuses can help me understand it. Thank you for your help

  • $\begingroup$ Just to clarify, does "valid graph" mean "tree" in the problem statement? $\endgroup$ – Alan Guo Oct 23 '12 at 0:36

The terminology is a bit bizarre, but it appears that valid graph here just means tree. Assuming that this is the case, you’re being asked to prove two things.

  1. Let $T_1,\dots,T_n$ be trees, and for $k=1,\dots,n$ let $v_k$ be a vertex of $T_n$. Let $v$ be a new vertex not in any of the trees $T_1,\dots,T_n$. Construct a new graph $G$ from the union of $T_1,\dots,T_n$ and $\{v\}$ by adding an edge from $v$ to $v_k$ for $k=1,\dots,n$. (In other words, you’ve tied the original $n$ trees together by running one edge from the new vertex $v$ to each of the trees $T_k$.) Prove that $G$ is a tree.

  2. Let $T$ be a tree, and let $v$ be a vertex of $T$. Let $G$ be the graph that remains when you remove $v$ and all edges incident at $v$ from $T$. Prove that $G$ is the disjoint union of trees $T_1,\dots,T_n$ for some $n$ (which may be $1$).

To prove (1) you must show that $G$ is connected and has no cycles; this is fairly straightforward. To prove (2) you must show that each of the connected components of $G$ is a tree, which just means proving that it has no cycles; this is almost trivial.

  • $\begingroup$ Thank you so much. This was a perfect response, would up rank if i had the rep. I think a lot of my confusion was being unsure whether valid graph meant tree $\endgroup$ – BadAtGraphs Oct 23 '12 at 18:07
  • $\begingroup$ @BadAtGraphs: You’re welcome. (What you can do, if you choose, is accept the answer by clicking on the checkmark beside it.) $\endgroup$ – Brian M. Scott Oct 23 '12 at 18: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.