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.

4
votes
1answer
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 ...
1
vote
1answer
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) = [5] 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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 \\ ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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 ...
4
votes
1answer
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$?
3
votes
1answer
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 ...
0
votes
1answer
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 ...
5
votes
1answer
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 ...
0
votes
1answer
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....
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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.
0
votes
1answer
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?
1
vote
2answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
108 views

Number of unlabeled rooted trees with n vertices and k leaves

I know that we can write the corresponding multivariate generating function as follows: $\sum y^kx^n$ such that $n$ is the number of vertices and $k$ is the number of leaves. Then we can obtain $f(x,y)...
3
votes
0answers
40 views

About a proof of a proposition about the spanning tree. I cannot understand.

I am watching this lecture about the minimum spanning tree now. Let $G = (V, E)$ be a (undirected) graph. Let $\mathcal{T} = \{T | T \subset E, (V, T) \text{ is a forest.} \}$. Let $M = (E, \...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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] ...
2
votes
0answers
56 views

Characteristic polynomial of a tree

I'm trying to understand the article: László Lovász, Jozsef Pelikan, On the Eigenvalues of Trees, Periodica Mathematica Hungarica, March 1973. I'm not sure I fully understand the proof of Lemma 1: if $...
1
vote
1answer
47 views

Almost all trees are cospectral (Allen Schwenk's 1973 article)

I am currently working on the following article: https://www.researchgate.net/publication/245264768_Almost_all_trees_are_cospectral. There are a few things that I don't understand, and since the ...
0
votes
0answers
9 views

Calculating maximum number of splits that can occur during insertion of $n$ keys in B Tree of order $m$

(I dont know if this question is valid candidate for math.stackexchange, but puttin it anyway as I believe this might require maths expertise) I can calculate this by trying out manually inserting $n$...
3
votes
1answer
39 views

How can I show that there will be at most $4^{n+1}$ pairwise non-isomorphic trees on $n+1$ vertices?

Prove that there exist at most $4^n$ pairwise non-isomorphic trees on $n$ vertices. I proceed by Induction, Let $n=1$ then we have only one tree on $1$ vertex which is less than $4$. Now assume ...
1
vote
0answers
46 views

Does the Graceful tree conjecture refer to all or only some trees?

I am a total beginner in this field and i‘m not really versed in the terminology, so please bare with me. What I know, is that a graceful labeling, refers to a tree with $n$ vertices, where each ...
2
votes
1answer
90 views

Spanning trees for complete graph

Let $K_n = (V, E)$ be a complete undirected graph with $n$ vertices (namely, every two vertices are connected), and let $n$ be an even number. A spanning tree of $G$ is a connected subgraph of $G$ ...
0
votes
1answer
45 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
vote
1answer
46 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 $T$, we have $2(n-1) = \sum _ { v \in T } d ( v )$, with $n$ ...
0
votes
1answer
24 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
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: ...
2
votes
2answers
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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'...
1
vote
1answer
27 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
48 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 ...