World's most popular travel blog for travel bloggers.

[Solved]: Constructing a tree from disjoint graphs

, , No Comments
Problem Detail: 

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.

Asked By : BadAtGraphs

Answered By : Luke Mathieson

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback