# 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,223 questions
128 views
+50

### 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 ...
19 views

### Graph Theory - Trees, Forest, Connected graph with 1 cycle.

I am struggling with visualizing this question. Suppose G is a simple graph with vertices V(G) =  and d(1) = 2, d(2) = 1, d(3) = 2, d(4) = 1. What is d(5) if G a forest with 2 components? A ...
54 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 ...
40 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 ...
20 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 \\ ...
33 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 ...
20 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 ...
38 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 ...
30 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 ...
19 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 ...
24 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 ...
31 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 ...
51 views

### Fixed points of a group action on tree

Suppose a group $H$ acts on a tree $T$, and this action fixes a point. Let $T_1$ be an $H$ invariant subtree of $T$. How do I show that $H$ fixes a point in $T_1$?
43 views

### How to prove that total number of non-isomorphic labelled trees of order $n$ is $n^{n-2}$?

I predicted the formula by finding total number of non-isomorphic labelled trees of order 1 is 1 , order 2 is 1,order 3 is 3,order 4 is 16,order 5 is 125.But how do i prove it ? I am beginner in graph ...
19 views

### Appropriate uses for Venn diagrams and Tree diagrams

I am really confused with expressing different types of events using probability trees and venn diagrams. Is it possible to represent dependent events using a venn diagram? I know it can be shown ...
64 views

### Transient random walk on 3-color 3-regular tree

Suppose that $T=(V,E)$ is a 3-regular tree with root $0$. Suppose that $0$ is colored green. All other vertices are colored blue, red or green, such that each vertex has exactly one neighbour of each ...
23 views

### Is adding k edges to spanning tree will result a graph with k cycle bases?

The number of cycle bases of a connected graph with $n$ vertices and $m$ edges is $m - n + 1$. Let's say, $v_k$ is the number of cycle bases of a graph resulting from adding $k$ edges to spanning tree....
20 views

### Nodes at height h of an n-element d-ary heap

I want to determine the number of nodes at height, $h$ of an $n$-element $d$-ary heap. Let $N_h$ represent the value I'm looking for. I've bounded $N_h$ but I can't seem to reduce it to equality. I ...
24 views

### Proof of property of spanning trees

I am looking at a proof of the following property: "If graph T had order n, T is a tree if and only if it contains no cycles, and has n-1 edges." The proof of <= is as follows: Suppose T is a ...
20 views

### Prim's algorithm loop invariant

Given an undirected graph G. At every step of Prim's algorithm, is the tree constructed so far an MST of nodes covered by Prim's? Can we prove this by contradiction or something? Or is there a ...
37 views

### total number of spanning trees in a connected graph

Suggest a method for determining the total number of spanning tree in a connected graph without listing them.
37 views

### Can you construct a graph if you are given all its spanning trees? [on hold]

Can you construct a graph if you are given all it's spanning trees? How?
96 views

### Expected distance between leaf nodes in a binary tree

Let T be a full binary tree with $8$ leaves. (A full binary tree has every level full). Suppose that two leaves a and b of T are chosen uniformly and independently at random. The expected value of the ...
31 views

### Can someone check my proof for: If a tree T has maximum degree k, then it has at least k leaves.

I have seen some proofs on this website for this problem using degree counting, but I was wondering if we could use induction? My proof is as follows: Base Case: $n = 2$ vertices Here, the number of ...
19 views

### How to calculate binary tree node number and layer number generated from $10^{100}$

Trying to learn about calculations related to binary trees, and would like to know how many binary tree node layers there are in a binary tree generated from $10^{100}$, and more generally, how to ...
33 views

### Minimal Spanning Tree With Algorithms

So I have a homework problem as above. The topic covered in class before this homework was Dynamic Programming. I have very little clue about what the question is actually asking: what is the MST ...
108 views

21 views

### Directed Trees Question Help

For part (a), I assume we build some version of a minimal spanning tree. Instead of the total sum of edges being minimum, the path from s to every vertex must be minimal. Is there a way to reduce this ...
62 views

### Generating the $n^{th}$ full binary tree over $N$ labeled leaves

I am looking for an algorithm to incrementally generate distinct full binary trees over $N$ unique leaves. That is, I want an algorithm that can generate the $n^{th}$ distinct tree without generating ...
22 views

### Computing coefficients of the generating function counting trees with forbidden members

How can I compute the coefficients $r^{(n)}_p$ with a Python code using the following equations? \begin{equation}\label{10} r^{(n)}(x)= S^{(n)}(x)-\frac{1}{2}\left[ (S^{(n)}(x))^2-S^{(n)}(x^2)\right] ...
56 views

34 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: ...
41 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 ...
20 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 ...
34 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 ...
21 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 ...
23 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 ...
16 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 ...
44 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'...
### 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 ...
### 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 ...