Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [trees]

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.

0
votes
0answers
11 views

Build a graph with uniform distribution [on hold]

I have 1000 points with (x,y,z) coordinates. From each node, beginning from (0,0,0) coordinates, 4 branches may be progressed to other nodes. The length of each branch should be less than ...
0
votes
2answers
22 views

Find number of leaves of a tree (Proof)

Problem: Let $T$ be a tree that has $i\ge1$ branch nodes, all of which have the same degree[1] $d$. Show that the number of leaves $(l)$ of the tree can be calculated via the following formula: $$l=(...
0
votes
1answer
75 views

What is the equivalent of a tree for directed graphs?

A tree is defined as a connected acyclic undirected graph at page 171 of this online book. What is the equivalent of a tree for directed graphs? A connected acyclic directed graph (i.e. a connected ...
0
votes
1answer
22 views

Number of spanning trees on graph disjoint union. [duplicate]

Consider a graph G on 200 vertices, created by adding the following edges $(v_1, v_{101}), (v_2, v_{102})$ to the disjoint union of two complete graphs $K_{100}$ with respective vertices $v_1,...v_{...
0
votes
2answers
36 views

Find the number of spanning trees of a graph

Let $n=2k+1$, where $k ∈ℕ$. Let there be two non-intersecting paths $a_1,a_2,...,a_n$ and $b_1,b_2,...,b_n$. Let us also add edges $a_1b_1$, $a_{k+1}b_{k+1}$ and $a_nb_n$. Find the number of ...
1
vote
1answer
19 views

Prove that a tree with two vertices of degrees $k$ and $l$ has at least $k + l - 2$ leaves

Let there be a tree with at least two vertices. One vertex has degree $k$ and the other has degree $l$. Prove that such tree has at least $k + l - 2$ leaves. My logic is that from one vertex you ...
0
votes
1answer
19 views

Let G be a connected graph and let T1 and T2 be spanning trees of G. Let e be an edge of T1

Hi I am trying to prove the following : Let G be a connected graph and let T1 and T2 be spanning trees of G. Let e be an edge of T1. 1) Show that T1 \ {e} has exactly two components. 2) Show that ...
0
votes
1answer
33 views

Red-Black-Tree Insertion & Deletion Complexity proof

I'm struggling with two propositions in my algorithms book. I'm unsure how to proof this. The insertion is abolutely logical that it takes up to O(log(n)) recoloring and at most one restructuring (as ...
0
votes
0answers
24 views

A tree in which all subtrees are of size $2^k-1\;$ for some $\;k\in\mathbb N$ is balanced

I'm trying to prove the following: Given a binary tree $\,T\,$ if every subtree is of size $2^k-1\;$ for some $\;k\in\mathbb N$, then $\,T\,$ is balanced. I've tried to disprove this but then ...
2
votes
1answer
57 views

Find number of trees with $\deg(v) = 1$ or $\deg(v) = 3$

Find number of trees where $$ \forall{v}, \text{ }\deg(v) \in \left\{1,3 \right\} $$ Generally I have idea for recurrence there: $$t_n = n\left( t_{n-1} + \sum_{a,b,c \in \mathbb{Z_+} \wedge a+b+c = ...
5
votes
1answer
41 views

binary search tree with key values $ a_1 < \dots < a_k$. How do I choose $j$ to still get a tree with minimal height?

So at the beginning I have an empty binary search tree. Moreover I have key values $a_1 < \dots < a_k$. How can we choose $j$ so that after the first insert of an element with key value $a_j$ a ...
0
votes
0answers
9 views

Is showing all trees have $\rho$-valuation not enough to prove Ringel's conjecture about trees decomposing odd complete graph?

This might be a soft question, but I am trying to understand graceful labeling ($\beta$-valuation) and all the related stuff, and I have read Rosa's paper too. I would like to know why most are ...
1
vote
1answer
43 views

Geometric realisations of trees are Cat(0)

I am trying to prove the title of this post. I have already looked into this post: $\mathbb{R}$ -trees are CAT(0) space But this does not cover the possibility where the geodesic triangle in the tree ...
2
votes
1answer
25 views

Find number of all spanning tree of $G_n$

Find $d_n$ which is number of all spanning tree of $G_n$ where $V = \left\{ 0,1,...,n \right\} $ and $$E = \left\{ \left\{ 0,i \right\} : i \in [n] \right\} \cup \left\{ \left\{ i,i+1 \right\} : ...
4
votes
1answer
77 views

In Huffman coding, how do I choose the frequency to get the maximum average bit length?

First I want to give you a little summary about the Huffmann code to avoid misunderstandings. Summary begins So we have an alphabet $A$ with $|A| > 1 $. For example $A$= {$a,b,c,d,e$}. Now we ...
3
votes
1answer
58 views

Searching for an equation (and proof of this equation) for internal path length and external path length

I already know and proved the following statement: Let $B$ be a binary tree and we want an extended binary tree. Then the following equation holds: $$ E = I + 2 \cdot |V| $$ where $E$ is length ...
2
votes
0answers
36 views

Probability Distribution Function of the Height of Nodes in Full Binary Trees

I would like to understand the distribution of node heights in the space of full binary trees with a fixed number of leaves, $n$. That is, given a random full binary tree with $n$ leaves how likely is ...
-1
votes
1answer
40 views

Connected Graph MST

There are 100 towns labelled with 1, 2, ..., 100. We want to connect them all and it costs max{|i − j|, 4} to build a bridge between town “i” and “j”. However, when it comes to a bridge between town i ...
0
votes
1answer
16 views

Is the boundary of a rooted tree with finite valence compact?

Given an infinite rooted tree $T$ with root $v$ it is possible do define the boundary $\partial T$ of $T$ to be the set of ininite paths emanating from $v$. If $T$ has bounded valence, then the ...
3
votes
1answer
80 views

Counting certain graphs defined over consecutive sets of natural numbers

Let $[n] = \{1,\ldots, n\}$ and call a subset $M \subseteq [n]$ a consecutive subset if $$M = \{m,m+1,\ldots,m+|M|-1\}$$ for some $m \in [n]$, i.e., $M$ contains a smallest and a largest number and ...
0
votes
0answers
32 views

Given weighted graph with several of unknown weights decide for every edge if in the MST .

I got this question : Given weighted graph with several of unknown weights ,decide for every edge if its in MST , not in MST or we dont have enough information to decide. I know that are few terms to ...
0
votes
2answers
34 views

Top leaves in a tree with probabilities on edges

Suppose I had a tree, where each edge had a probability assigned to it, and the probabilities all of the edges coming from a node sum up to 1. You could consider these probabilities to come a machine ...
1
vote
1answer
30 views

“Adding a linear number of vertices and edges”

Apologies for if this is a rather silly question, but the impetus for this question comes from the curious usage of the titular phrase within this conference paper right after the section entitled "2 ...
1
vote
1answer
20 views

$m$-Trees are Infinite.

Let $\Gamma$ be a tree, and $m \ge 2$. If $\Gamma$ is an $m$-tree (all vertices have valence of $m$), then $\Gamma$ is infinite. My idea is to prove it by contradiction. Suppose that $\Gamma$ is ...
0
votes
0answers
31 views

Equivalent Characterizations of Trees

First some definitions: An edge path, or more simply a path, in a graph consists of an alternating sequence of vertices and edges $\{v_0,e_1,v_1,...,v_{n-1},e_n,v_n\}$ where $Ends(e_i) = \{v_{i-1},...
0
votes
0answers
31 views

Minimum sum of leafs in a weighted binary tree

I was wondering what the minimum sum of the weights of leaves in a binary tree with weighted paths and $n$ leaves is. The weight of a path going right incurs a weight of $r$, while going left incurs a ...
8
votes
1answer
124 views

Uniqueness of spanning tree on a grid.

When I was at the Graduate Student Combinatorics Conference earlier this month, someone introduced me to a puzzle game called Noodles!. The game starts with a collection of "pipes" on a grid (...
2
votes
2answers
54 views

Find the number of degree 1 vertices in terms of n and d

Fix an integer $d>1$. Let $G$ be a tree with $n$ vertices, and every vertex can have either degree $1$ or $d$. Find the number of degree $1$ vertices in terms of $d$ and $n$. I've been working on ...
1
vote
1answer
47 views

Why is this induction wrong on Trees?

I just learned it in class that when using induction to prove a tree problem, we should always remove a vertex instead of adding one in induction. Why is that? For example, prove that tree with $n$ ...
3
votes
1answer
70 views

Relation between sorted weights of spanning tree and minimal spanning tree

Let $ G=(V,E) $ be a graph, $T$ a minimal spanning tree for $G$ and $T'$ some spanning tree of $G$. Let us denote: $w_1\leq w_2\leq ... \leq w_{n-1}$ the weights of $T$ $w'_1\leq w'_2\leq ... \leq ...
1
vote
1answer
74 views

Find a formula, in terms of n and k , for the number of leaves of G.

Let G be a tree having n n vertices. Suppose that every vertex in G which is not a leaf has degree k, where k > 1 . Find a formula, in terms of n and k , for the number of leaves of G. I started ...
0
votes
0answers
16 views

Divisor Gonality On Graph - Induction Proof

I am working with Divisor Gonality on graph, particularly Tree. The gonality of tree is 1. I would like to prove this with Induction Method for study purpose. Does anyone suggest any concept that I ...
1
vote
1answer
48 views

Generalizing a formula for enumerating rooted k-ary trees from doing so with ternary trees?

Recently I worked on a problem that involved finding the total possible rooted, labeled ternary trees with n vertices. After doing some math and using Lagrange inversion I found a formula for the ...
2
votes
0answers
30 views

Prove that if $\delta(G)+ \Delta(G)+1 \geq \left|V\right| $ then G is connected

I have been give this problem and asked to solve it in less than 8 minutes, I failed. I would appreciate your approach to the solution much more than the solution itself and any recommended exercice ...
1
vote
2answers
104 views

Proving that : $ \frac{W(x)}{xe^x}=\sum\limits_{n=0}^{\infty} \frac{(-1)^n}{n!}T(n)x^n $ [closed]

How to prove that: $$ \frac{W(x)}{xe^x}=\sum_{n=0}^{\infty} \frac{(-1)^n}{n!}T(n)x^n $$ where $T(n)$ counts the number of forests of rooted labeled trees using labels in a subset of $\{1,\ldots,n\}$...
0
votes
1answer
31 views

maximum spanning tree

I wonder how to prove that given a Minimum Spanning Tree of a graph, the other spanning tree with the least common edge with Minimum Spanning Tree is always Maximum Spanning tree.
3
votes
0answers
36 views

Height of the Uniform Random Tree

Consider $\mathcal{T}_n$ the uniform rooted labelled tree on $n$ vertices (i.e. each spanning tree on $K_n$ has the same probability to be picked, and the root is picked uniformly among the $n$ ...
1
vote
1answer
205 views

FFT: Multiplying multiple poynomials in O(KSlogS) time

I have a problem where I have to use the Fast Fourier Transform (FFT) algorithm $K$ polynomials $P_1,...,P_K$ where $\mbox{deg}(P_1) + · · · + \mbox{deg}(P_K) = S$. I have to show that I can find the ...
0
votes
0answers
41 views

Binary tree of Multipeg Tower of Hanoi

I've come across to this problem Show the solution of Multipeg tower of hanoi $(n,p) = (361,8)$ in a binary tree, where $n$ = number of disks, $p$ = number of pegs I know how multipeg tower of ...
4
votes
1answer
175 views

Equal coloring of balanced ternary tree

Given a complete balanced ternary tree (every leaf is at the same depth) where every edge has length $1$. An equal coloring is a coloring of the edges in red and black (each edge can be broken up into ...
2
votes
2answers
61 views

Can we have an infinite tree in this graph?

Suppose that a graph has an infinite number of nodes set up as follows: let $V_n=\{a_{n,1},a_{n,2},\dots,a_{n,n-1}\}\cup\{b_n\}$ be a set of $n$ nodes. Let $V=\bigcup_{n=1}^\infty V_n$. I am ...
0
votes
1answer
66 views

How to Show a graph is 3-connected?

I am attempting to solve a proof given in class which states the following: A cubic tree is a tree whose vertices have degree either 1 or 3. Let T be a cubic tree and let G be a cubic graph obtained ...
0
votes
0answers
21 views

Proof by contradiction for edge in tree

I have a problem from my textbook that goes like the following; Assume that i have a shortest path matrix $S$ that could look like the following: $$ S=\begin{bmatrix} 0 & 1 & 2 & 6 \\ ...
1
vote
0answers
40 views

Almost all trees have non-trivial automorphism group

In their paper Asymmetric Graphs Erdős and Rényi proved that almost all trees have non-trivial automorphism group. More specifically they showed that almost all trees contain at least one so-called ...
1
vote
0answers
21 views

Support of functions on trees.

We define a tree $T$ to be a poset $(T,\leq)$ such that $\forall x\in T$, the set $\{y\in T|y\leq x \}$ is well-ordered. Consider partial functions $f:T\rightarrow T$ such that the domain of $f$ is ...
1
vote
2answers
40 views

Basic arboricity example

I'm having some trouble proving two interesting properties of arboricity of a graph. Arboricity is defined as the minimal number of forests into which a graph can be divided, and it can also be ...
1
vote
1answer
40 views

Half-catalan numbers

I've been interested in counting how many binary trees there are with n leaves. I consider 2 trees to be the same if I can swap the children of nodes to get the other one. I've started by figuring ...
1
vote
0answers
20 views

Proving a formula for the amount of pendant nodes in a tree

I'm trying to prove the following, but I am not sure if my approach can be accepted as a mathematical proof. Let $T$ be a tree with $n \ge 2$ nodes. Prove that the number of pendant nodes (nodes ...
3
votes
1answer
25 views

Determine all the trees (on at least two vertices) which are isomorphic to their complement.

Determine all the trees (on at least two vertices) which are isomorphic to their complement. Hello graphed 4 trees and found onle two which are self-complementary ones. They are Tree with 1 vertex ...
0
votes
0answers
47 views

Prove that a B-Tree of N keys has N+1 leaves

Let B be a B-tree of order m, containing N items. Prove by induction that B has N+1 leaves. I know that you should use induction on the depth of the tree, but how? EDIT: The properties of a B-Tree ...