For questions about trees in graph theory, which are connected graphs with no cycles. Also can be used for questions about forests, which are graphs that are disjoint unions of trees.

learn more… | top users | synonyms

1
vote
0answers
13 views

Proof for the number of leaves for any Binary Search Tree

A property for binary trees is that the number of leaves is the number of full nodes plus 1, in other words, $L = F + 1$ where $L$ is the number of leaves and $F$ is the number of full nodes. What ...
0
votes
1answer
11 views

How would I find a minimum weight spanning tree for W?

If I were to let $W$ be the weighted graph formed by taking a complete graph $K_5$ on five vertices 1, 2, 3, 4, 5 with the weight of each edge $\{x,y\}$ given by $(\{x,y\}) = x + y$, how would I find ...
-1
votes
1answer
28 views

Question about trees, Let T be a tree with n vertices

Are my answers correct to these 3 questions? Let T be a tree with n vertices. 1) What is the average degree/valency of the vertices in T? Average Degree of of ...
0
votes
1answer
29 views

How many spanning trees does the cycle graph C2014 have?

How many spanning trees does the cycle graph $C_{2014}$ have? How do I create a bipartite graph and use it to solve this problem?
1
vote
1answer
7 views

Postorder and Preorder traversal on a Binary tree

For the tree below, list the labels of the nodes of the tree according to the pre-ordering algorithm, and then re-list them according to the post-ordering algorithm. ...
1
vote
1answer
35 views

Graph theory: tree vertices

How can I calculate the number of vertices of a tree knowing he has 33 vertices of degree 1, 25 vertices of degree 2, 15 vertices of degree 3 and all other vertices of grade 4?
0
votes
1answer
35 views

Spanning tree with unique paths.

Let $G$ be a connected graph and let $r∈V(G)$. Prove that $G$ has a spanning tree $T$ such that for every edge of $G$ with ends $u$ and $v$, either $u$ belongs to the unique path in $T$ with ends $v$ ...
3
votes
1answer
19 views

Proving every tree has at most one perfect matching

In trying to prove that every tree, T, has at most one perfect matching, I came across this idea: ...
4
votes
1answer
24 views

Expected number of subtree removal in a tree.

I was solving this problem. In a gist the problem is as follows: You are given a rooted tree. On each step you choose a node randomly and remove the subtree rooted by that node and the node ...
-1
votes
1answer
238 views

How to convert parentheses notation for trees into an actual tree drawing? [closed]

Trees are usually drawn as a set of objects connected by edges. But sometimes one sees a non-graphical, parentheses-based notation, like on the example below. What does the indentation mean in such ...
0
votes
1answer
17 views

Normalization of data in decision tree

After reading through a few references, I have come to know that for machine learning in general, it is necessary to normalize features so that no features are arbitrarily large ($centering$) and all ...
0
votes
1answer
19 views

The intersection of $k$ subtrees of a tree $T$ is nonempty.

Let $T_1$, $T_2$, . . . , $T_k$ be subtrees of a tree such that any two of them have a vertex in common. Prove that they all have a vertex in common. Any hints/solutions are greatly appreciated. I am ...
0
votes
0answers
46 views

prove that for all h in N, a height balanced tree has a height of at least 1.6^h

prove that for all h in N, a height balanced tree has a height of at least 1.6^h. Can this be proven by induction?
0
votes
1answer
28 views

Find the node that we will reach with a given path on a graph (complete binary tree)

This question is regarding a special case of graph i.e. complete binary tree Consider the following tree :- ...
1
vote
2answers
165 views

Prove that if all edge-costs are different, then there is only one cheapest tree.

Prove that if all edge-costs are different, then there is only one cheapest tree (minimum spanning tree). (Use contradiction and make sure to keep track of the costs of the different trees involved.) ...
2
votes
1answer
296 views

Number of binary trees with N nodes

I am trying to calculate the number of trees (non isomorphic) with n nodes (total including leaves). I think that there are n! such trees, but I don't know how to prove that. I know that the number ...
2
votes
1answer
33 views

Preorder Traversal

For Each Preorder Traversal, we have multiple Inorder Traversal. this is True or False Conclusion? every one would help me and add some detail.
2
votes
1answer
38 views

Visiting Node in BFS and DFS in the same order [closed]

if G be a connected, undirected graph and has at least 3 vertex. we know the order of visiting node from a given vertex in BFS and DFS is the same. which of the following is false? a) G can be a ...
3
votes
2answers
2k views

Finding number of homeomorphically irreducible trees of degree N

There is a scene in Goodwill Hunting where professor challenges students with task of finding all homeomorphically irreducible trees of degree 10. This is discussed in many places, such as here and is ...
3
votes
1answer
33 views

Shortest path between two vertex

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)? thanks to all.
1
vote
1answer
23 views

A graph with minimum degree $k+2$ contains any $(k+3)$-vertex tree as a subgraph?

Let $k$ be a positive integer and let $T$ be a tree of order $k+3$. If $G$ is a graph with minimum degree at least $k+2$, prove that $G$ contains a subgraph isomorphic to $T$. Any solutions or hints ...
0
votes
0answers
19 views

Pascal's Identity and Trees

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
3
votes
1answer
29 views

Automorphism of Tree

Let $\sigma$ and $\theta$ be two automorphisms of tree $X$. I want to show that min$_{v\in V(X)}d(v,\sigma(v))=$min$_{v\in V(X)}d(\theta^{-1}\sigma\theta(v),v)$. I know every automorphism of tree is ...
1
vote
1answer
57 views

Iterations of Pascal's Identity

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
7
votes
2answers
448 views

Is the graceful labeling conjecture still unsolved?

From the Wikipedia article on graceful labeling: ... A major unproven conjecture in graph theory is the Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that ...
3
votes
1answer
116 views

Virtually infinite cyclic groups act on a tree

A virtually infinite cyclic group $G$ is quasi-isometric to $\mathbb{Z}$ and thus has two ends; by Stallings theorem, $G$ acts (without inversion) on a tree with finite edge-stabilizers. But the ...
0
votes
1answer
28 views

How to understand the perfect binary tree formula?

I got this paragraph by reading "python algorithm", in which it mentioned `some knights participate in an knockout match, how many mathes do they need to produce the winner. It's answer says: I'm ...
14
votes
2answers
299 views

Does every “balloon” (dragon, tadpole, canoe paddle) admit a graceful labeling?

8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes. ...
3
votes
0answers
37 views

What are the algebraic and topological properties of a tree (graph theory), and what are any possible connections?

I'm a non-mathematician working with trees (mostly rooted and oriented trees). Typically, I understand them as join-semilattices, so they have an implicit algebraic structure: they form a subgroup ...
2
votes
1answer
95 views

How to establish bijective between the set of rooted trees and natural numbers, using Godel numbering?

Consider the structure of a rooted tree independent of its underlying set, (i.e. in the sense of trees as combinatorial species). I know a number of ways which we can encode any such tree in natural ...
2
votes
1answer
55 views

Infinite Tree Probability Question

Suppose I have 10 dollars and I'm able to make fair 50/50 bets like flipping a coin. Now suppose each bet is for 1 dollar. What is the probability that if I keep making bets until I hit 0 dollars ...
-1
votes
1answer
108 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
0
votes
3answers
39 views

How to write a summation function that counts the number of nodes in a tree?

I come from a programming background and am interested in learning how to represent some things as simple equations, as an entry into thinking mathematically. How do you represent a tree structure as ...
0
votes
1answer
42 views

Width and height of binary tree is $\theta(n)$?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
0
votes
0answers
14 views

Tree of arity n: How to call a vertex that has only k (k<n) children?

What is the correct adjective for a vertex in an n-ary tree that has only k children (k < n)? I was thinking of something like "unsaturated", but I don't know if that is the correct word for this. ...
0
votes
1answer
30 views

Number of distinct Binary tree formed with respect to height h

How many types of distinct Binary Tree can be formed with a height of h? assuming height starts from 0 when the tree has only the root. example: if the height of tree is 1 then root-leftchild ...
0
votes
1answer
21 views

Proof about spanning tress in graphs

Let $G=(V,E)$ be a graph and $T_i=(V,F_i),i=1,2$ two disjoint spanning trees in $G$. Let $f_1 \in F_1$. Prove that there is $f_2\in F_2 $ such that $T:=T_1-f_1+f_2$ is a spanning tree.
0
votes
0answers
21 views

How does inserting N objects one at a time into an ordered AVL tree yield an efficient sorting algorithim

If we assume reblalancing an AVL tree of height n after an insertion or deletion takes O(n) operations. How does inserting N objects one at a time into an ordered AVL tree yield an efficient sorting ...
0
votes
2answers
45 views

Prove that if G is a tree in which all vertices have odd degree then G has odd size.

Prove that if G is a tree in which all vertices have odd degree then G has odd size. Good night, do not know how to approach this "prove". Can you give me tips to solve it?. Please.
0
votes
1answer
23 views

Formula for number of “root” nodes in a tree where Parent shares child nodes?

If I have a tree like this: {a},{b,c},{d,e,f},{g,h,i,j} in this case we have a total of 10 nodes. Is there any equation where given "10" I can calculate how many bottom nodes there are (answer: "4" ...
1
vote
3answers
75 views

Proof of an $\iff$ statement on binary trees

Let $x$ and $y$ be two nodes of a binary tree $B$. Prove that $x$ is an ancestor of $y$ $\iff$ $x$ stands before $y$ in the pre-order traversal of $B$ and $x$ stands after $y$ in the ...
0
votes
1answer
34 views

How to compute a marginal probability

Given a weighted graph, using the Kirchhoff's matrix tree theorem, how can I compute the marginal edge presence probability: $$P_\beta(ij)=Z_\beta^{-1}\sum_{\text{T spanning tree:$(i,j)\in ...
0
votes
2answers
51 views

Why is the height of a heap defined as $\lg n$?

I'm a bit confused about why the height of a heap (or a binary tree in general) is given by the floor of $\lg n$. E.g. if you have a tree with 7 nodes, you would get $h = 0$ instead of $h = 2$. Isn't ...
0
votes
0answers
38 views

Min. Spanning Tree - Same weight

Prove that every minimum spanning tree of a connected graph, $G$, has the same maximum edge. Intuitively, this makes sense to me. You need to have that heavy edge because that is the cheapest ...
0
votes
2answers
51 views

Tree with $k$ edges is a subgraph of any graph with all vertices of degree $\geq k$.

Let $T$ be a tree with $k$ edges. Let $G$ be a graph where every vertex has a degree of at least $k$. Show that $T$ is a subgraph $G$. I know this implies that in a graph where every vertex is at ...
2
votes
1answer
53 views

How to call a tree with a single branch?

How do you call a tree with only one branch (in other words, where every vertex has maximum one direct successor)?
0
votes
1answer
24 views

Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance
0
votes
2answers
31 views

Number of spanning trees of a graph (behind the formula)

Given $G$ a subgraph of $K_n$ s.t. $G$ has $n$ vertices with adjacency matrix $A$; why is $$\sum_{T \text{ spanning tree of }K_n}\prod_{(i,j)\in T}A_{i,j}$$ the number of spanning trees? I can't get ...
1
vote
1answer
134 views

Number of rooted subtrees of given size in infinite d-regular tree

Currently I am reading a paper where the author states: [...] It is well-known that an infinite $D$-regular rooted tree contains precisely $\frac{1}{(D-1)u + 1} \binom{Du}{u}$ rooted subtrees of ...
3
votes
0answers
41 views

Proof on Dyadic Trees [Smullyan: First-Order Logic, chapter 1, section 0]

I'm having difficult with a proof from Smullyan's First-Order Logic, Chapter 1 Section 0 (Reprint, Dover 1968, p. 4): Prove: In a dyadic tree, define x to be to the left of y if there is a ...