3
$\begingroup$

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 $X_1, X_2, \dots, X_i$ of disjoint valid graphs by adding a new node adjacent to one node from each of $X_1,\dots, X_i$. 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 one 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 can help me understand it.

$\endgroup$

migrated from cstheory.stackexchange.com Oct 23 '12 at 3:41

This question came from our site for theoretical computer scientists and researchers in related fields.

3
$\begingroup$

The reverse direction is relatively straight forward, as we start with disjoint vertices, and at each step only add edges to a new vertex, we cannot introduce a cycle, furthermore at each step we connect the "graph so far", so we finish with a connected graph.

For the forward direction, we just need to consider how we could construct a tree in such a manner. The key observation being that a subtree is also a tree. Thus we can recursively break down a tree (the construction is then a series of applications of adding a new node and some edges) by picking a vertex in the tree, and taking each of its subtrees as the sets $X_{1},X_{2},\ldots$. Each of these is a tree (and hence "valid"), so we can construct them in the same manner. Eventually we reach a set of leaves (individual vertices) which are by definition "valid".

Tree construction from valid subtrees, adding a new vertex connecting them.

The diagram gives a little sketch of this, with the "valid" components $X_{1}$, $X_{2}$ and $X_{3}$ all representing trees, with a new vertex added, and a single edge from each component to this new vertex.

$\endgroup$
  • 2
    $\begingroup$ Both directions are essentially induction proofs. $\endgroup$ – Raphael Oct 23 '12 at 9:14
  • $\begingroup$ This is so helpful. thank you so much. I think one of my problems was that I wasn't confident to make the jump that "valid graph" meant "tree" $\endgroup$ – BadAtGraphs Oct 23 '12 at 18:05

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.