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
2answers
29 views

Trees-related proof

I just began my Graph Theory course, so I'm pretty knew in this area, at least when it's about formal proofs(I have some experience on intuitive level, implementing certain algorithms related to graph ...
1
vote
1answer
39 views

Leftish Heap and Its Right Spine

Purely Functional Data Strutures presents the following question: Chapter 3, Question 1: "Prove that the right spine of a leftist heap of size n contains, at most, floor ( log ( n + 1) ) ...
1
vote
3answers
47 views

Traversing through a binary tree

Consider a full binary tree of n nodes numbered from 1 to n in the common top-down left-to-right manner. For the sake of the ...
3
votes
2answers
122 views

Find a Generating Function for Ordered Rooted Ternary Trees

The Full Question If we let $T=$ the family of rooted ternary trees, $t_n =$ be number of trees in $T$ with $n$ nodes and $T(x) = \sum\limits_{n=0}^{\infty}w_nx^n$ be the generating function of $T$. ...
6
votes
4answers
151 views

What is the number of full binary trees of height less than $h$

Given a integer $h$ What is $N(h)$ the number of full binary trees of height less than $h$? For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't ...
0
votes
0answers
22 views

Determining whether two trees are isomorphic

Is there a (probably recursive) algorithm that can be used to determine whether two not necessarily binary ordered (sub)trees are isomorphic or not?
2
votes
1answer
88 views

Number of rooted subtrees with m edges of a p-regular tree

I have the following question: Assume I have an infinite $p$-regular tree, that is a tree where every node has degree $p$ (so also the root should have degree $p$). Then how many subtrees containing ...
0
votes
0answers
50 views

Proving number of leaves in $m$-ary tree.

Prove that a full $m$-ary tree with $i$ internal vertices has $l=(m-1)i +1$ leaves. I'm having trouble finding any good information about $m$-ary trees online I've got a few pictures but they don't ...
1
vote
0answers
26 views

Adjacency of vertices from Prufer sequence

Is adjacency of vertices can be known from Prufer sequence without decoding? Thanks!
6
votes
7answers
400 views

EGF of rooted minimal directed acylic graph

I am trying to find the exponential generating function of directed minimal acyclic graphs (which I now call dag), where every non-leaf node has two outgoing edges. Context: A simple tree ...
1
vote
1answer
14 views

Get number of vertices when number of internal vertices is known ofr a full binary tree

But I can find a counter example: * / \ * * / \ / \ * * * * Here $k = 2$, but number of vertices is 6, and number of terminal ...
1
vote
1answer
114 views

How to check homeomorphic embedding relation programmatically?

This is a follow up to this question and Deedlit's answer. I'm looking for a precise definition of the "hem?" (tree A homeomorphically embeddable in tree B?) relation, preferably in terms of a ...
2
votes
1answer
93 views

Prove that the vertex degree of a minimum spanning tree is in $\mathcal{O}(1)$

I have given a set of points $S$ in $\mathbb{R}^2$. From the this points I create a mininum spanning tree MST. The euclidean distance of the points is used as the weight for the edges. The ...
3
votes
5answers
24k 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 ...
3
votes
0answers
109 views

Associativity of the tensor product of dendroidal sets

For any smal category $A$, I shall write $\widehat A$ for the category $[A^{\text op}, \mathbf{Set}]$ of presheaves on $A$, and $y_A\colon A \to \widehat A$ for the Yoneda embedding relative to $A$. ...
2
votes
1answer
139 views

Relax function on Bellman Ford Algorithms

In a Weighted Directed Graph $G$ (with positive weights), with $n$ vertex and $m$ edges, we want to calculate the shortest path from vertex $1$ to other vertexes. we use $1$-dimensional array $D = ...
2
votes
1answer
175 views

what is an “edge disjoint spanning tree”?

if there are n = 2 vertices in a connected graph, i am supposed to have "n/2 edge disjoint spanning trees". This means i should have 1 edge disjoint spanning tree for a n = 2 graph? My best guess ...
0
votes
1answer
25 views

Graph Theory: proof about the number of vertices in a Tree's component

I'm having some problem understanding the question below: Let T = (V,E) be a tree. Show that T has a vertex v such that for all e that exists in E, the component of T-e containing v has at least ...
1
vote
0answers
91 views

How to find the number of connected components of a graph by using its 16x16 adjacency matrix?

Good day, I have this exercice that provides me with the 16x16 matrix of adjacency of a graph and it asks me to find the number of connected components of the graph and I need to give a spanning tree ...
1
vote
2answers
66 views

Rooted Tree and Greedy Algorithms

In a Rooted Tree, we have a message on Root. in each step, each node that has a one copy of message, can transfer this message to at most one of it's childeren. we want to use minimum step and send ...
1
vote
2answers
1k views

Convert a tree to a forest where every component has an even number of vertices.

I have the following problem, which I am struggling with. It asks to find the maximum number of edges to be removed from a tree to convert it to a forest, where every component will have an even ...
4
votes
2answers
135 views

Some equivalence relation from flipping binary trees

I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
2
votes
0answers
71 views

Graph Algorithm and Cycle Detection

In $O(|V|+|E|)$, we can detect whether a Directed Graph has a cycle or not. ---> True In depth-first seach on DAG, there is no Back Edge. ---> True With known Number of Edges, in $O(|V|)$ and not ...
1
vote
1answer
112 views

Remove edge from tree, number of vertices

Prove that if $T$ is a tree on at least $k+1$ vertices and max degree at most $d$, then there exists an edge $e$ such that the removal of $e$ causes $T$ to split into two trees where at least one of ...
2
votes
3answers
120 views

In a Tree, show that the largest degree of a node <= number of nodes of degree 1

Let $T$ be a tree in which the largest degree of a node equals to $t$. Let $n_1$ denote the number of nodes of degree $1$ in $G$. Prove that $n_1 ≥ t$ I understand why this works but I am not sure ...
2
votes
0answers
57 views

Counting unlabeled and non-uniquely labeled trees

I recently learned about Cayley's formula, which states that the number of trees on $n$ labeled vertices is $n^{n-2}$. As I understand it, this works because we can prove that there are $n^{n-2}$ ...
0
votes
1answer
83 views

Prove by induction that every complete $k$-ary tree of depth $n$ has $(k^{n+1}–1)/(k-1)$ nodes for all integers $n\ge 0$, where $k\ge 2$.

A strictly $k$-ary tree is a $k$-ary tree (a binary tree is a $2$-ary tree) in which every node has either no children (is a leaf) or $k$ children. A complete $k$-ary tree of depth $n$ is a ...
0
votes
1answer
70 views

Huffman coding - conditions for perfect tree output

The question is: Given 4 characters and their frequencies, what's the max possible difference between the frequency of the rarest character and that of the most common character, so the output Huffman ...
2
votes
0answers
71 views

Examples of forcings which add no “definable” Aronjain tree

Maybe a bit board question but: Fixing a regular cardinal $\kappa$ in the ground model, I am looking for examples of set forcing notions which preserve regularity of $\kappa$ and add no new $\kappa$ ...
0
votes
2answers
41 views

Binary search tree. Counting.

How many BSTrees can be constructed from given set: $\{1,2,3,4,5\}$? I have no idea how to solve it. Please help me. Thanks in advance.
1
vote
1answer
249 views

Induction Proof Check: For a binary tree T, Prove that the number of full nodes in T is always one less than the number of leaves in T.

This is a slight variant on a very common beginner's problem. I think I've got it figured out, but I wanted to make sure I actually proved what's being asked. We define a binary tree $T$: (a) A tree ...
1
vote
1answer
42 views

Determine if there is a node in a binary postorder anti-sorted tree with key $k$

A binary postorder anti-sorted tree is a binary tree for which the post-order traversal gives the keys that are saved at the nodes of the tree in descending order. Present a pseudocode for the most ...
3
votes
1answer
42 views

Identifying Binary Search Trees from their Prufer Sequence

If you ignore its root, a Binary Search Tree generated by some permutation of $\{1, \ldots, n\}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found ...
0
votes
0answers
12 views

Changements that have to be done in order to delete node of red-black tree

According to my lecture notes: Let $x$ be the child of the node that we delete. Let $w$ be its sibling node and $p$ the father of $x$. There are four cases: At the first case, $w$ is red. We ...
0
votes
1answer
115 views

Draw a 2-3 tree, insert and delete a key

Assume that at the nodes of a 2-3 tree, the following keys are saved (in an increasing order): $3,6,9,12,15,18,21,24, 27, 30, 33, 36$. It is also given that the root is a 2-node that contains the ...
3
votes
5answers
6k views

How many edges does an undirected tree with $n$ nodes have?

How many edges does an undirected tree with $n$ nodes have?
0
votes
1answer
26 views

Is these Trees isomorphic or not?

Is these Trees isomorphic or not? They have same structure but they have different code. Because one of them is minimum code. Thank you for your answers in advance.
1
vote
1answer
103 views

Discrete math - Prove that a tree with n nodes must have exactly n - 1 edges? [duplicate]

I'm new in discrete math. Can someone prove simply that a tree with $n$ nodes must have exactly $n - 1$ edges. I have researched the solution but I haven't founded yet. I know of course, a tree with n ...
1
vote
1answer
37 views

Rotations after inserting element in AVL-tree

We want to insert $58$ at the following AVL-tree and then we have to make rotations so that the tree is balanced. According to my notes, we are at the case RL (The first edge leads to the right and ...
0
votes
0answers
72 views

$T(n) = T(n/3) + T(2n/3) + cn$ - recursion tree with constance $c$

I have a task: Explain that by using recursion tree that solution for: $T(n)=T(\frac n3)+T(\frac 2n3)+cn$ Where c is constance, is $\Omega(n\lg n)$ My solution: 1. Recursion tree for $T(n)=T(\frac ...
0
votes
3answers
99 views

Proving if $G$ has no cycles but by adding one edge between any two vertices will create a cycle then $G$ is a tree

Prove: if $G$ has no cycles but by adding one edge between any two vertices it will create a cycle then $G$ is a tree. Below is the definition we use for a tree. I don't see any way to connect ...
3
votes
1answer
34 views

Height of quasi-complete binary tree

Let us define a quasi-complete binary tree as a rooted binary whose nodes have all two children except at most those of the penultimate level, which can have either one or two children. I read that ...
0
votes
1answer
181 views

Let $G$ be a connected graph, then $G$ is a tree iff $G$ has no cycles

Prove the following: Let $G$ be a connected graph, then $G$ is a tree $\iff$ $G$ has no cycles. $\Rightarrow$ If $G$ is connected and a tree then by the definition of tree it has no cycles. ...
2
votes
0answers
44 views

Delete nodes that satisfy a property

I want to write a function that takes as argument a pointer A to the root of a binary tree that simulates a (not necessarily binary) ordered tree. We consider that each node of the tree saves apart ...
1
vote
1answer
13 views

Prove in any tree with n vertices, the number of nodes with 3 or more neighbors is at most 2(n-1)/3

I know that the number of edges in the tree is n-1, and by the sum identity, the degree is 2(n-1)... I'm not sure how to go about completing the proof, or even starting it for that matter.
2
votes
1answer
42 views

Graph with fixed amount of spanning trees

"Find a graph with 8 vertices, which have exactly 27 spanning trees." How do I find such a graph, or prove one does not exist?
0
votes
0answers
25 views

Isomorphism testing for minimal SP-trees

I'm doing a bit of research on the SP-trees. I'm still new to this whole problematic, so I'd be thankful if someone cleared this thing up. :) This is the scenario that I'm trying to come up with a ...
0
votes
0answers
16 views

$k$-ary labeled trees with distinct labels

Classical definition of $k$-ary labeled trees doesn't restrict somehow the uniqueness of tree labels inside its branches. My question: Is any special definition (name) for such trees? To clarify ...
5
votes
2answers
1k views

Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
0
votes
0answers
168 views

Terminology, mapping a tree to a tree

I have stumbled upon a problem; unfortunately, I do not know the proper terminology to be used which hinders me in thinking about the problem and explaining the problem. I am not even sure this is the ...