Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Just to clarify, does "valid graph" mean "tree" in the problem statement? –  Alan Guo Oct 23 '12 at 0:36

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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 –  BadAtGraphs Oct 23 '12 at 18:07
    
@BadAtGraphs: You’re welcome. (What you can do, if you choose, is accept the answer by clicking on the checkmark beside it.) –  Brian M. Scott Oct 23 '12 at 18:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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