Stack Exchange Network

Stack Exchange network consists of 174 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.

1
vote
0answers
22 views

How is the spanning tree constructed in the Minimum Cost Flow Problem?

Could someone please explain how the spanning tree was constructed? Notation aclaration. $[40]$ denotes the supply on node $A$. $[-30]$ denotes the demand on node $D$. $c_{AD}=9\iff 9$ denotes the ...
0
votes
1answer
42 views

Graph Theory - Trees

I recently read the answer to a question regarding the difference between a tree and a spanning tree. The following is the link: Difference between a tree and spanning tree?! Now we know that the ...
-1
votes
0answers
19 views

How many Left binary trees of height h exist?

I know the recursion for finding a Binary trees of height h: NT(h) = 2NT(h-1)*(NT(0)+NT(1)+NT(2)+...+NT(h-1))-NT^2(h-1) Base cases: h=0 -> 2 h=1 -> 3 What is the recursion for finding How many ...
1
vote
1answer
34 views

Find the number of trees on $2m$ given vertices in which all vertices have degree $1$ or $3$.

Problem: Find the number of trees on $2m$ given vertices in which all vertices have degree $1$ or $3$. My attempt: We know that for a tree $2(n-1) = \sum _ { v \in T } d ( v )$, with n the number of ...
0
votes
1answer
18 views

Find the bounds of the number of leaves in a tree

Problem: Let $n ≥ 3$ be an integer, $T$ be tree on $n$ vertices, with no vertex of degree $2$, and m be the number of leaves in $T$. It is true that we always have one of the following: $m \geq ( n + ...
2
votes
1answer
30 views

The number $F(n,k)$ of forests on the vertex set $[n]$ having $k$ components and such that $1, . . . , k$ belong to distinct components?

Problem: What is the number $F(n,k)$ of forests on the vertex set $[n]$ having $k$ components and such that $1, . . . , k$ belong to distinct components? Solution given by the professor Janos Pach: ...
-1
votes
0answers
19 views

Finding a solution using backward induction for the game shown in tree

there is a exercise in Game Theory(Decisions, Interaction and Evolution) by James N Webb (Exercise 5.1), the question is "Finding a solution using backward induction for the game shown in Figure 5.2?" ...
2
votes
2answers
36 views

Example of a Tree with

In my lecture of combinatory, there is this theorem : T is a Tree $ \iff $ T has on edge less than the number of vertices and it is acyclic. I'm confused because it appears to me that if there is at ...
0
votes
0answers
17 views

Represent a binary tree in one dimension

Is there a way to represent a binary tree in one dimension that preserves relative distance between any two nodes? (Distance is the number of edges on the path from one node to another). If not, how ...
1
vote
2answers
26 views

Could a graph of order $n >2$ with two vertices of degree $n-1$ be a tree?

I need to answer to this (apparently) simple question. In my opinion, since a tree has $n-1$ edges, a graph with these characteristics couldn't exist. In fact, whatever $n$ is chosen, I don't know ...
0
votes
0answers
19 views

The tree of $SL_2$ over a local field

I’m studying Chapter II: $\mathbf{SL}_2$ of Serre’s book “Trees”. In paragraph 1, Serre defines the tree of $SL_2$ over a local field $K$. In particular, he considers the set of $\mathcal O$-lattices ...
0
votes
1answer
19 views

Proof on undirected graph/ minimal spanning tree

I have an undirected simple graph $ G=(V,E)$ with $V= \{1,...,n\}$ and $ w: E \rightarrow \mathbb{R} , w(e_{ij}):=i+j$ I want to show, that $ (V,T)=(\{1,...,n\},\{ \{1,2\}, \{1,3\},....,\{1,n\}\})$ is ...
1
vote
0answers
13 views

Is there a specific way to handle equations to convert it into such a form that it gives right value for any value substituted?

I was trying to find relation between total number of nodes in a complete binary tree and the leaf nodes. Note that a complete binary tree is a binary tree in which every level, except possibly the ...
0
votes
0answers
42 views

Prove $F(n+2) - 1 = 1 + n(h-1) + n(h-2)$ by mathematical induction

$F(0)= 0$ and $F(1) = 1$ are predefined; $F(n)$ references the $n^{th}$ Fibonacci number. $n(h)$ is the minimal number of nodes needed to construct a AVL binary tree of height $h$. The theory shouldn'...
1
vote
1answer
18 views

A given arboresescence is a shortest path tree if and only if $ d_B(r,v) \leq d_B(r,u) + l(u,v)$

Definition Let $D = (V, A)$ be a directed graph, with $r \in V$. Suppose that a directed path from $r$ to $v$ exists, for every $v \in V \setminus {r}$. An r-arborescence in D is by definition a set ...
2
votes
1answer
43 views

Is the infinite regular tree $T_\infty$ quasi-isometric to the $n$-regular tree $T_n$?

It is known that for $n\geq 3$ all $n$-regular trees $T_n$ are quasi-isometric to each other. This can e.g. be seen by using an edge contraction argument. Is there also a quasi-isometry between the ...
0
votes
0answers
20 views

Is there a specific search paradigm for finding pairs in a set?

I'm dealing with a very common problem in computer programming that involves, for example 4 people to be divided into 2 pairs. Mathematically, this is just a permutations problem, and the number of ...
0
votes
1answer
18 views

proving that a graph has only one minimum spanning tree if and only if G has only one maximum spanning tree

Is this claim true? I thought about it and it seems true but for proving it i started with one direction by assuming that i have one minimum spanning tree and i want to show that from this i have also ...
6
votes
3answers
235 views

Find most even trisection of a tree graph in O(n) time

I have been working on this for a few days, brushing up on graph theory and disjoint sets, but I have not yet found an algorithm that is guaranteed to produce the optimal result and runs in better ...
0
votes
2answers
25 views

Proof - A tree $T$ has a vertex of degree n and the others have degree $<n$. T has at least n leaves

I tried to think about some characteristics of the trees, for example, they have a number of edges equal to $|\text{Vertices}|-1$ and of course the handshaking lemma but I couldn't find properly ...
1
vote
1answer
103 views

Pardon my ignorance, but isn't TREE(3) a finite number?

Pardon my ignorance, but isn't TREE(3) a finite number? -Dylan Thurston It is my understanding as well that TREE(3) is finite (Proof that TREE(n) where n >= 3 is finite?). However, I have seen ...
1
vote
1answer
28 views

Can a tree graph have only one vertex? And if so, that means that a tree graph has at minimum one leaf?

Also, if the tree is two vertices connected by an edge, does the root count as a leaf too? Since it's also a vertex of degree one? I've had trouble clarifying this online and from my textbook. Thank ...
0
votes
1answer
38 views

How does hyper-plane equation divide vector space into cells convex polyhedrons?

I came across some specific algorithm that divides high-dimensional vector space into non-overlapping cells of convex polyhedron. It does this by using tree based binary partitions (which might not ...
2
votes
1answer
37 views

Optimal Tree Labelling

I am trying to solve the following problem : For a tree $T = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges. A label $L$ of $T$ is an application from $T$ to $\{0,1\}^{|V|}$. ...
1
vote
1answer
35 views

Infinite “connected” graphs and spanning trees

Let us say that graph $G$ is quasi-connected iff for every two vertices there is either a finite path or an infinite path in sense of the offtopic of this answer. Assuming the axiom of choice, is it ...
0
votes
1answer
30 views

Coloring binary tree edges with given number of colors

Let's say I have a balanced binary tree which has 37 leaves.I can color the vertices of this tree with 37 colors. $$ 37 * 36^{72} $$ ways. How can I find out coloring edges with 37 colors? Original ...
0
votes
0answers
14 views

How many are there trees with n vertices, that have degrees d1, d2, …, dn

I am trying to find out how many there are trees like in this question: Sufficient conditions on degrees of vertices for existence of a tree
3
votes
1answer
36 views

Suppose T is a tree with degree sequence 5, 5, 5, 4, 4, 3, 3 plus several 2’s and 1’s. Find the number of leaves of T.

Suppose T is a tree with degree sequence 5, 5, 5, 4, 4, 3, 3 plus several 2’s and 1’s. Find the number of leaves of T. I currently have made this much progress. Let $x$ be the number of degree $2$ ...
0
votes
1answer
17 views

Equivalent Definition of a Tree Graph Theory: Restriction for Being Connected?

I was looking at some equivalent definitions of a tree in graph theory and one is the following where we let $G$ be an undirected graph: $G$ is a tree iff $G$ is connected and has $n-1$ edges where $...
0
votes
1answer
38 views

How to prove that height of a rooted tree is an invariant under isomorphism?

Intuitively, if we're restricted to mapping the root of $T_1$ to the root of $T_2$ that makes the structure of the two trees rigid. And since under isomorphism the number of vertices are equal, height ...
0
votes
0answers
17 views

Binary Search Trees

Create a binary search tree for these library titles: A Duck is a Duck Enslaved by Ducks Mini Ducks Songbook Fowl-Weather Friends Big Dig Ducks Regarding Ducks and Universes Domesticated Ducks ...
1
vote
1answer
110 views

Number of rooted trees

Compute the number $t_n$ of rooted trees with n nodes described by the following equation: We know that we cannot construct such tree for all $n$ (where $n$ is natural number). For example, we can ...
1
vote
0answers
35 views

Necessary conditions for a tree to have a Hamiltonian path

What is a necessary condition for a tree to have a Hamiltonian path? I assume the solution to this question is that a tree can only have two leaves because if there are 3 vertices who have degree 1, ...
1
vote
0answers
10 views

Reduction of Steiner Tree to Maximum Weight Connected Subgraph

I want to proof that the MWCS is an NP-hard problem by proofing that its decision version is NP-Complete. Below I have my proof so far and I hope people can give comments whether it can be formulated ...
1
vote
0answers
20 views

Order of choosing keys from the given sets to insert in B+ tree

The question is taken from web.stanford.edu. Consider a B+ Tree where each node can have at most $3$ keys. Suppose the tree initially has a root node with two children leaf nodes, which contain ...
1
vote
1answer
42 views

Binary trees constructed from the bottom up

I'm dealing with a set of random binary trees which I can't find referenced anywhere in literature. Computer scientists seem to prefer "random search trees" which is a different ensemble than mine (...
1
vote
1answer
32 views

How many trees are there on vertex set $[n]$ that contain a given edge $uv$? [duplicate]

How many trees are there on vertex set $[n]$ that contain a given edge $uv$? If we glue the vertex $u$ and $v$ with an edge then there are $n-1$ vertices and using the Cayley's formula there are ...
0
votes
1answer
35 views

Suslin trees in transitive models

Let $M$ be a transitive model of $ZFC$ with $\omega_1\in M$ such that $M\models ((T,<)\text{ is a Suslin tree})$. Fix $A\in M$ such that $M\models (A\text{ is a maximal antichain})$ and $b\subset T$...
1
vote
2answers
33 views

What is in the minimum number of simple paths in a forest of k trees with n vertices?

I'm stumped on this one. Let G be a forest containing 6 trees with 27 total vertices. What is the minimum number of simple paths for G? I know how to compute this for an even number of vertices. For ...
0
votes
0answers
12 views

Binary search tree with minimum potential

How to construct a n-node binary serach tree such that its potential is the minimum? The size, rank and potential are defined as follows The size $s(v)$ is the number of nodes in a subtree (include v)...
3
votes
1answer
25 views

A conjecture about minimal spanning trees among points in the unit square

For $n\in\Bbb N$, consider $n$ points $x_1,\ldots, x_n$ in the unit square $Q=[0,1]^2$. Let $f(x_1,\ldots, x_n)$ denote the minimal total edge length of a tree with $x_1,\ldots, x_n$ as vertices. Let ...
1
vote
0answers
13 views

Isometric embedding probability distributions with tree transportation cost into $\ell_1$

I was trying to solve the following problem, but don't quite know how to get started with working with the transportation metric. Let $T = ([n], E)$ be an unweighted, undirected tree with root $r \...
1
vote
0answers
14 views

What is the lower bound of number of degree 1 vertices of a tree with no degree 2 vertices?

Here is the question: Let $G$ be a tree with $n$ vertices, and no vertex in the tree has degree $2$. Find a function of $n$ that indicates the lower bound of the number of degree $1$ vertices in ...
0
votes
1answer
13 views

Is my graph and tree proofing correct for this degree sequence?

I was wondering if you could help verify if my answer is correct. The question is: Is (1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 4, 5) a degree sequence of a graph? Is it a degree sequence of a tree? ...
3
votes
2answers
45 views

tree has exactly $k$ nodes with degree $4$. Show that this tree has $2k+2$ leaves.

Prove: If a tree has exactly $k \geq 1 $ nodes with degree $4$, then this tree has at least $2k +2 $ leaves. ( nodes with degree $< 4 $ are only allowed for the leaves ). So I think that we can ...
-1
votes
1answer
147 views

Show that $M_k(G)$ is the set of independent sets of a matroid! [closed]

Let $G = (V,E)$ be an undirected graph. Set $M_k(G) = (E,S)$ where $$S = \{F ∪M | F ⊆ E,(V,F) \;\text{acyclic},M ⊆ E,|M| ≤ k\}.$$ Show that $M_k(G)$ is the set of independent sets of a matroid! In ...
0
votes
0answers
25 views

Trees for which the Prufer code is a strictly monotone sequence

Problem: Find the number of trees on n labeled vertices such that the corresponding Prufer code is a strictly monotone sequence. So far I tried with some small Prufer code : (1,3,5) or (1,2,3) and in ...
0
votes
0answers
47 views

Number of spanning trees in a bipartite graph

I want to prove that in a complete bipartite graph with vertices $1,..,m$ and $m,..,m+n$, we have $n^{(m-1)}m^{(n-1)}$ spanning trees. Therefore I thought about the matrix tree theorem which states ...
0
votes
1answer
23 views

Tree of order $p$ with $p_i$ vertices of degree $i$ for $i\in\{1,\dots, p-1\}$.

Let $T$ be tree of order (number of vertices) $p$ and with $p_i$ vertices of degree $i$ for each $i\in \{1,\dots, p-1\}$. I am asked to prove that the following equation is satisfied: $p_1=\sum_{i=3}^...
0
votes
0answers
81 views

What is the relationship between the external path length, internal path length and total number of nodes of a full ternary tree?

The closest proof I can find is for full binary tree, but I don't understand the last step, i.e. how he links the external path length, internal path length two variables together. Proof