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

3
votes
2answers
94 views

How many vertices does this tree have?

Suppose that $T$ is a tree. It has $e$ edges and $n$ vertices, and $\overline{T}$ has $10e$ edges. What is n? I think $n = 1$ is a solution, because $T$ can have no edges then, so $0=10*0$. A ...
0
votes
1answer
74 views

Parse Trees - Arithmetic Expressions

In regards to the right side of this expression (c * (a-b)) how is it factored to include (-) instead of * and then (-) again? I cant understand what steps my teacher made to do this.
4
votes
1answer
67 views

Infinite sequence of trees that are not subgraphs to each other

This is from a set of exercises and I am stuck to this. Please, have in mind, that I want to understand how it's solved, I am not just looking for a solution. Define an infinite sequence of trees ...
0
votes
1answer
98 views

Binary Search Tree Traversals

Draw a BST when you insert, $O,V,E,R,F,L,C,W$ from left-to-right and determine the order of the nodes when using post-order traversal and pre-order traversal. My attempt at drawing the BST: ...
0
votes
0answers
40 views

Can an arbitrary network of nodes be effectively visualized as a circular “treemap”?

We all know that a treemap is effective for visualizing hierarchical tree data (i.e. where there are only 1 to many relationships like in a computer file system): But how difficult algorithmically ...
8
votes
2answers
216 views

Ordinal interpretation of Friedman's $n$?

I heard that Kruskal's tree theorem can be turned into a finite form that creates an extremely fast growing function because ordinals could be encoded into trees. On this wiki page it mentions that ...
2
votes
1answer
92 views

questions about binary search tree

Show that every n-node binary search tree is not equally likely (assuming items are inserted in random order), and that balanced trees are more probable than straight-line trees. How is it prove ...
0
votes
2answers
95 views

A tree $T$ with 50 end-vertices has an equal number of vertices of degree 2, 3, 4, and 5 but contains no vertices of degree greater than 5.

What should be the order of $T$? So I know a graph $G$ is a tree if every two vertices of G are connected by a unique path
1
vote
1answer
38 views

Graph G with two Spanning Trees

Let's assume that Graph $G = <V,E>$ has two Spanning Trees $G_a = <V, T_1>$ and $G_b = <V,T_2>$ where $T_1 \cap T_2 = \emptyset$ and $T_1 \cup T_2 = E$. Prove that $\chi(G) \le 4$ ...
5
votes
1answer
89 views

Finding graphs with a given number of spanning trees

All of the graphs considered in this question are connected. We can find the number of spanning trees $t(G)$ of $G$ using Kirchhoff's matrix-tree theorem or the deletion-contraction method. I'm ...
1
vote
1answer
119 views

Find Minimal Spanning Tree Using Prim's Algorith

What will be the minimal spanning tree using Prim's Algorithm for this graph Also can i draw a tree and assign the weights as i like,will there be a minimal spanning tree for such a graph
0
votes
1answer
49 views

Some questions about first-order logic (arising from a book by Raymond M Smullyan)

Recently, I got confused when reading a book about first order logic written by Raymond M smullyan. Chapter 1 page 9:When introducing the notion "Formation tree", smullyan define a formation tree for ...
1
vote
0answers
59 views

Proof of existing path on Depth-First-Search spanning tree

Let $G$ be an undirected connected graph, and $T$ the directed spanning tree of $G$, which I got by performing a DFS on $G$. If $H$ is a complete subgraph of $G$, how can I proof that there a path in ...
1
vote
2answers
45 views

Proof that spanning trees can be converted into one another

Let $T_1$ and $T_2$ be two spanning trees of a graph $G$. Prove that if $e$ is an edge of $T_1$, there exists an edge $f$ in $T_2$ so $T_1-\{e\}+\{f\}$ also is a spanning tree. For $\{e\}\subset ...
2
votes
2answers
60 views

Construction Types or Type Constructions?

In any (simple) type theory there are base types (i.e. the type of individuals and the type of propositions) and type builders (i.e. $\rightarrow$, which takes two types $t,t'$ and yields the type of ...
0
votes
1answer
46 views

Finding the parent of a node in recombining binomial tree

I have posted an earlier question: Finding the child node in the recombining binomial tree. Now I would like to find the parent of a node in recombining tree. The tree looks like this: Now I need ...
1
vote
0answers
301 views

Finding a spanning tree using exactly k red edges in a graph with edges colored by red/blue in linear time.

So we have a graph $G$ with its edges colored by red and blue. we are asked to find a deterministic linear time algorithm that given a parameter $K$ finds a spanning tree of G using exactly $K$ red ...
1
vote
1answer
77 views

The complement of spanning trees is covered by a union of cycles

Is it true that in any (connected) graph $G=(V,E)$, if $T$ is a spanning tree than its complement (edge-wise) may be covered by a union of disjoint cycles? Here's a non-complete attempt to prove this ...
0
votes
1answer
50 views

Proofs with binary trees [duplicate]

Now I have a binary tree which is How would I go about proving binary tree with $n$ leaves has exactly $2 n - 1$ nodes ?
0
votes
1answer
580 views

Number of nodes in binary tree given number of leaves

How would I prove that any binary tree that has n leaves has precisely $2n-1$ nodes ? Given that a binary tree is either a single node "o" or a node with the left and right subtrees contains a binary ...
1
vote
1answer
54 views

Variance of Height of Tree

What is the asymptotic variance of the height of rooted plane trees (ie rooted, unlabelled, ordered trees with unbounded node degree) and of ordered binary trees (ie rooted, unlabelled, plane trees, ...
2
votes
0answers
36 views

What are the automorphisms of an $n$-regular tree?

Let $T$ be the connected tree in which each vertex has $n$ neighbors. (So $T$ is infinite.) What is the full automorphism group of $T$?
0
votes
1answer
79 views

Are the structure of logical expression based on formative constructions like sequences or trees ?

Recently, I get confused when reading the book Principles of Mathematical Logic written by D. Hilbert. How to define the term 'logical expression'? I just envisage that it might be defined as anyone ...
2
votes
1answer
42 views

Number of trees of a certain size

Given a branching factor $b$ and a tree height $h$, a complete tree has $\sum_{i=0}^h b^i$ nodes. Define a partial tree as a sub-tree of the complete tree, with the same root. How many such partial ...
0
votes
2answers
630 views

creating a Binary tree based on a prefix expression

I want to find the value of a the prefix expression -/+8,10,2*3,2 and build its binary tree I am trying to learn this for a math course, but have absolutely no clue ...
1
vote
1answer
184 views

What is the fairest solution/formula for rewarding points in a hierarchical network?

Introduction The nature of this hierarchical network is based on the concept of Multi-Level Marketing strategy. Example 1 - Unfair Situation Ancestor receives 1 point for every descendant ...
1
vote
2answers
45 views

How to go from Tree to Total orders

Given a tree $T=(X,E)$, is it guaranteed for any orientation of the edges $E$, there exist a strict total order preserves it? For instance, let $X=\{x_1,x_2,..x_n\}$ and $E=(x_i,x_{i+1})$ the result ...
2
votes
1answer
50 views

Counting problem (should use Cayley's formula)

How many trees above $V=\{1,2,3,4,5,6,7,8,9\}$ are there, such that $deg(4)=5$? I know I should use Cayley's formula somehow.
0
votes
0answers
21 views

Can a search-tree be reversed in order to find more solutions?

consider a search-tree that we already know that if we start from the start-node (S), and go to nodes A1, B2, C1, then we get to the Goal-node. We have this solution, but we don't know the other nodes ...
3
votes
1answer
131 views

A Graph as a Union of K forests.

I want to show that a graph G that is a union of k forests has a chromatic number of at most 2k. I have narrowed my problem down to trying to show that any graph G that is a union of n trees has a ...
0
votes
2answers
106 views

syntax tree for the word (())()()

I have to create the syntax tree for the word (())()() . That's what I have tried: Could you tell me if it is right?
5
votes
2answers
710 views

How many vertices of degree 1 in a tree?

How many vertices of degree 1 are there in a tree with no vertices of degree more than 4? The only thing that I have right now is that the number of edges in a tree is n-1 where n is the number of ...
0
votes
2answers
72 views

Determining number of parent node on an n-tree.

I'm sorry if this is the wrong one, was unsure if this was computer science, programming, or mathematics related. I'm going with mathematics because it is semi-graph theory related. I have a tree ...
1
vote
0answers
16 views
0
votes
1answer
87 views

How to prove this necessary and sufficient condition for tree in graph theory?

Let $0<d_1\leq\ldots\leq d_n$ be integers. Show that there exists a tree with degrees $d_1,\ldots,d_n$ if and only if $d_1+\ldots+d_n=2n-2$.
3
votes
1answer
169 views

Understanding countable ordinals (as trees, step by step)

Even though ordinal numbers – considered as transitive sets – are perfect non-trees, it is worth (and natural) to visualize them as trees, starting from the finite ones which are given as ...
0
votes
1answer
61 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
0
votes
2answers
155 views

Use strong induction to prove number of vertices on complete tree is $2l-1$

Can someone help me construct this proof using strong induction? Use strong induction on $l$ to show that for all $l \geq 1$, a full binary tree with $l$ leaves has $2l-1$ vertices total.
0
votes
1answer
38 views

Transforming spanning trees through a sequence of intermediate trees

the problem is as follows: Let $G$ be a connected graph, and let $T_1$ and $T_2$ be two of its spanning trees. Prove that $T_1$ can be transformed into $T_2$ through a sequence of intermediate trees, ...
0
votes
1answer
106 views

proof: center of a tree lies on the longest path

how can I make a proof of this property? I mean, given a weighted tree(with positive costs), how can I proof that the center of such a tree lies on the longest path?? I read to the first answer of ...
0
votes
1answer
49 views

Recursive trees

Use the method of recursive tree to determine a good asymptotic upper bound (as tight as possible) for the following recurrence and prove your answer using induction (assuming that $T(n)$ is a ...
1
vote
2answers
127 views

How to prove that the smallest asymmetric tree has at least 7 vertices?

Find the smallest possible number of vertices an asymmetric tree can have (i.e. prove that no smaller tree can be asymmetric). I think that the answer is 7, but I don't know how to prove it.
1
vote
0answers
152 views

Software/Applet to Draw Tree Diagrams (for Enumeration Problems)

I need a software/applet/flash file which easily draws tree diagrams for simple enumeration problems: I want to give number of the vertices in each layer, and it draws the diagram which shows all the ...
1
vote
1answer
38 views

Number of binary trees with same X-order and Y-order

What is the number of binary trees which have the same X-order and Y-order as the given tree? Example: X-order: POSTORDER(T) = POSTORDER(TL) POSTORDER(TR) root Y-order: ANTIORDER(T) = ...
0
votes
1answer
60 views

Non-Isomorph trees of a graph

Please consider this graph How many non-Isomorph trees with 4 vertex has this graph? Is there any formula that show number of non-Isomorph trees with $n$ vertices? thanks
2
votes
5answers
13k views

The maximum number of nodes in a binary tree of depth $k$ is $2^{k}-1$, $k \geq1$.

I am confused with this statement The maximum number of nodes in a binary tree of depth $k$ is $2^k-1$, $k \geq1$. How come this is true. Lets say I have the following tree ...
0
votes
1answer
67 views

Depth of BFS Tree With Different Root Nodes

I need to either prove or disprove that for any node of a graph, the depth of the BFS tree using this node as root is always the same. My intuition is that this is true, but I'm having difficulty ...
2
votes
0answers
44 views

Number of nodes with even offspring

I've been working on a combinatorics assignment, and while the last few questions had clever solutions which didn't involve functional equations and the use LIFT, I fear I'm at my end. Given a ...
1
vote
1answer
33 views

Does the Prim algorith always create the same tree despite the starting node?

Does the Prim algorith always create the same tree despite the starting node? PD: sorry for my english.
0
votes
1answer
85 views

Inserting values left to right in a binary search tree

What does it mean to build a binary search tree by inserting values from left to right starting from an empty tree? The "left to right" part confuses me..I know how to build one by normally inserting ...