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.

Let's have two sets - $T_1$ and $T_2$ defined as below:

  • Def.1 : $T_1$={ T | T is a tree with at least one edge and T doesn't have vertices from 2 degree }

  • Def.2 : Every connected graph with exactly two vertices is in T2. For every such graph G({u,v}, {(u,v)} ) the sets of boundary vertices of G is {u,v}.

    • If $G(V,E)$ is a graph from $T_2$ and $U \subseteq V$ is the sets of the boundary vertices of $D$ and $z$ is a random vertix from $U$ and $W$ is a sets of vertices, such that $|W| \ge 2$ and $W \cap U $ = $ \emptyset $, so $G^\prime (V \cup{W}, E \cup {(z,w)|w \in W})$ is also a graph from $T_2$ and the sets of boundary vertices of $G^\prime $ is $(U${$z$}$)\cup W.$
    • $T_2$ doesn't have another graphs.

Using these definitions, prove that :

  1. $T_1 \subseteq T_2$
  2. $T_2 \subseteq T_1$
  3. Using $(1)$ and $(2)$ prove by induction , that for every tree with at least one edge(which doesn't have vertices from $2$ degree) is truth, that the number of vertices from $1$ degree is $ \ge n/2 +1$, where n is the number of all vertices.
share|improve this question
I've proved 1) and 2), but have stuck on 3)...Any ideas? –  DiscreteMath'sFan Jan 3 '13 at 8:26
Could you work on editing the grammar and spelling? I do not understand "doesn't have vertices from degree two", "for every three", –  Calvin Lin Jan 3 '13 at 8:36
For def 2, point 1, are you simply trying to say that the complete graph $K_2$ is in $T_2$? For point 2, What is $W$? Is it allows to be in $V\setminus U$? Is it possibly outside of $V$?? What is $(U{z})$ mean??? –  Calvin Lin Jan 3 '13 at 8:42
At this moment, I cannot understand what you're trying to say. Definition 2 is incomprehensible to me, and I cannot guess what you're trying to say. Someone else might have better luck. I believe that "for every three (the number 3)" actually means "for every tree (graph theory)" –  Calvin Lin Jan 3 '13 at 8:47
ah :), of course that this actually means, sorry I fixed it –  DiscreteMath'sFan Jan 3 '13 at 8:52

Your Answer


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

Browse other questions tagged or ask your own question.