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

2
votes
1answer
175 views

spanning trees of an edge transitive graph

Let $G$ be an edge transitive graph. Let $t(G)$ be the number f spanning trees on $G$. Show that each edge lies in exactly $\tfrac{(n-1)t(G)}{m}$ spanning trees. Where $|V(G)|=n$ and $|E(G)=m$. $\...
2
votes
1answer
1k views

Number of distinct path in a graph with $n$ vertices

Let $T = (V , E)$ be a tree with $|V | = n\geqslant 2$. How many distinct paths are there (as sub graphs) in $T$? I already have the answer to this question as $(n/2)$. The problem that I'm having is ...
2
votes
1answer
105 views

A way to codify (pre-calculatate) if a one Tree Node is a descendant of another

I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing): What I need is a ...
2
votes
2answers
4k views

Proof by induction and height of a binary tree

I need some help with a simple proof. I want to know if this proof is correct: Let's define the height of a binary tree node as: 0, if the node is a leaf 1 + the maximum height of the children ...
2
votes
4answers
7k views

Minimum Number of Nodes for Full Binary Tree with Level $\lambda$

If the level ($\lambda$) of a full binary tree at zero is just a root node, than I know that I can get the maximum possible number of nodes (N) for a full binary tree using the following: N = $2^{\...
2
votes
1answer
332 views

Evaluating 'combinatorial' sum

Help me please to calculate the following sum. I have seen such kind of formulas in the papers related to combinatorics, specifically 'trees'. I am curious how to calculate or approximate this sum: ...
2
votes
1answer
28 views

Question about theorem with trees

I know the theorem: for an undirected graph on $n$ nodes, any of the following two imply the third: $G$ is connected $G$ does not contain a cycle $G$ has $n-1$ edges (source) ...
2
votes
1answer
58 views

Shortest Path Via Dynamic Programming Formulation?

We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. for ...
2
votes
1answer
26 views

Find depth of three node tree

I am trying to write a formula to find the depth of a three node tree and having issues doing it. Each node will have an index number going from top to bottom, left to right. It will look something ...
2
votes
1answer
97 views

What is a “linear chain” in Graph Theory?

What is a linear chain in the context of graphs and trees? For example: a topological sort forms a linear chain What does a linear chain mean in the example above? Another example from ...
2
votes
2answers
312 views

How to find the number of all the possible ordered trees with n edges and k leaves?

We know that a tree with n edges have n+1 nodes.So if $|B_{n+1}|$ is the number of all possible ordered trees with n+1 nodes then its true that $C_{n+1} = |B_{n+1}|$ where $C$ is the Catalan number....
2
votes
1answer
70 views

Existence of infinite subsequence of trees with a special condition

For rooted trees, define $children(v)$ as the number of children of the vertex $v$. Assume two operations on rooted trees: contract an edge: choose an edge $E$, join two vertices adjacent to $E$ ...
2
votes
1answer
2k views

Longest Path in undirected unweighted graph

I came across a problem where I have to find out the longest path in a given graph. I have list of edges ( eg.{AB, BC} ) which states there is an edge between vertices/nodes (A,B,C). Now i want to ...
2
votes
1answer
108 views

A decision tree has an expected depth of at least $\log n!$

I am looking at the proof of the following theorem and I have some questions. The theorem is the following: On the assumption that all permutations of a sequence of $n$ elements are equally ...
2
votes
1answer
189 views

Infinite Tree Probability Question

Suppose I have 10 dollars and I'm able to make fair 50/50 bets like flipping a coin. Now suppose each bet is for 1 dollar. What is the probability that if I keep making bets until I hit 0 dollars ...
2
votes
1answer
317 views

Number of rooted subtrees of given size in infinite d-regular tree

Currently I am reading a paper where the author states: [...] It is well-known that an infinite $D$-regular rooted tree contains precisely $\frac{1}{(D-1)u + 1} \binom{Du}{u}$ rooted subtrees of ...
2
votes
2answers
88 views

Introductions to posets on algerbaic structures (Everything I need to know about them)

I need a good and complete introduction to Tree-like orders and partial orders on algebraic structures with one operations. I accept basic texts too. I'm looking for free online texts mostly because ...
2
votes
1answer
63 views

Number of trees of a certain size

Given a branching factor $b$ and a tree height $h$, a complete tree has $\sum_{i=0}^h b^i$ nodes. Define a partial tree as a sub-tree of the complete tree, with the same root. How many such partial ...
2
votes
1answer
86 views

Counting problem (should use Cayley's formula)

How many trees above $V=\{1,2,3,4,5,6,7,8,9\}$ are there, such that $deg(4)=5$? I know I should use Cayley's formula somehow.
2
votes
4answers
3k views

How many labeled trees exist on n vertices with exactly 3 vertices of degree 1?

My combinatorics class is covering spanning trees right now and one of the questions being asked is "What is the number of labeled trees on n vertices with exactly $3$ vertices of degree $1$?" I've ...
2
votes
1answer
148 views

Given an $n$ level tree with $b$ branches at each node, how many unique paths are there from the root to the leaves?

I have a tree where, at each node, it splits into $b$ branches for a total number of $n$ levels. I enumerate the paths from the root to the leaf nodes. For example, if $n = b = 2$ then I have the ...
2
votes
1answer
63 views

Is there a tree $T$ such that $\text{diam}(T) \geq k$, where $k$ is the number of vertices with degree less than 3?

Let $T$ be an undirected tree, let $d$ be the diameter of $T$, and let $s$ be the number of vertices in $T$ with degree less than 3. Recall the diameter of a graph is the length of the longest ...
2
votes
1answer
332 views

Length of Shortest Path in a Generated Binary Tree

Let's say I have a binary tree of $2$-tuples of positive integers starting with $(1,1)$. The left-child of any element $(A,B)$ is $(A,A+B)$, and the right-child of any element is $(A+B,A)$. Hence, the ...
2
votes
1answer
59 views

Counting the numnber of (labelled and unlabelled) rooted trees on $n$ vertices with height $h$

As far as I know, the number of labelled rooted trees on $n$ vertices is $n^{n-1}$. Is there a known result for counting the number of (labelled and unlabelled) rooted trees on $n$ vertices having ...
2
votes
1answer
18 views

What is the maximum number of “root subtrees” that a tree can have?

Let $T=(V,E)$ be a directed rooted tree with root $r \in V$. A root subtree$^1$ of $T$ is a directed rooted tree $T'=(V',E')$ that fulfills the following conditions: $T'$ is a subgraph of $T$, $r \...
2
votes
1answer
37 views

Graphs embeddable into tree like simplicial 2-complexes

A tree gives rise to a simplicial 1-complex. A tree like simplicial 2-complex would be simplicial 2-complex without any closed 2-subcomplexes (the analog of a cycle in graphs) and such that the 1-...
2
votes
1answer
44 views

Finding DFS in undirected graph

Consider the following sequence of nodes for the undirected graph given below. a b e f d g c a b e f c g d a d g e b c f a d b c g e f A Depth First Search (DFS) is started at node a. The nodes ...
2
votes
1answer
29 views

Different trees of weighted graph , please check whether my explanation is correct $?$

Let G=(V, E) be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in G. If S and T are two different trees with $\xi(S) = \xi(T)$, then ...
2
votes
3answers
180 views

Showing that the complete bipartite graph $K_{a,b}$ is a tree if and only if $a=1$ or $b=1$.

Let $K_{a,b}$ be the complete bipartite graph. Show that $K_{a,b}$ is a tree if and only if $a = 1$ or $b = 1$. The way my professor showed us for a complete graph is as below. I just don't know how ...
2
votes
1answer
127 views

Dual graph of a tree

It is stated here that: For any connected embedded planar graph G define the dual graph G* by drawing a vertex in the middle of each face of G, and connecting the vertices from two adjacent ...
2
votes
1answer
233 views

Furthest distance vertices undirected tree

I know in my mind that it's very obvious, but I just can't seem to prove the following statement: Let $G$ be an undirected non-trivial tree with at least $3$ vertices. Let $u$ be an arbitrary vertex ...
2
votes
1answer
169 views

what' is the number of full subtrees of a full binary tree?

I'm looking for the number of full sub-trees of a binary tree; all possible tress of height less than $4$ are: Now my question is: What is $N(h)$ the maximum number of full sub-trees of a ...
2
votes
1answer
153 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 ...
2
votes
1answer
219 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
2answers
401 views

Two disjoint spanning trees, spanning subgraph with all even degrees

Show that if a graph has two edge-disjoint spanning trees then it has a connected, spanning subgraph with all degrees even. I start by looking at the union of the two spanning trees. I know it has $...
2
votes
1answer
2k 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 ...
2
votes
1answer
70 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
43 views

Why doesn't Tutte polynomial T(1,1) equal 0?

If the formula for a Tutte polynomial is: then how does T(1,1) solve for spanning trees instead of just returning a 0?
2
votes
1answer
1k views

Preorder traversal, inorder traversal, postorder traversal

a) preorder traversal b) inorder traversal c) postorder traversal Ok, a) r,j,h,g,e,d,b,a,c,f,i,k,m,p,s,n,q,t,v,w,u b) a,b,d,c,e,g,f,h,j,i,r,s,p,m,k,n,v,t,w,q,u c) a,b,c,d,e,f,g,h,i,j,v,w,t,u,...
2
votes
1answer
625 views

Proving that the height of a 2-3 tree is between $\log_3 N$ and $\lg N$

I am stuck on the problem of trying to prove the upper and lower bounds of a 2-3 tree. I think the most natural recourse is to use induction. However, my instructor told me that this was unnecessary ...
2
votes
1answer
181 views

Find tree diameter or center

I want to find center in a graph that doesn't have cycles. I heard, that this is how I find a diameter: Take random vertex A Find such vertex B, that distance to it is maximal Find such vertex C, ...
2
votes
1answer
43 views

tree structure on classes of elements in GL_2 over a field with discrete valuation

this is my first question here, so I hope I am doing it right. :) I'm currently reading a paper about the tree of GL_2 over a discretely valued field (similarly to Serre). Here's the setting: $k$ an ...
2
votes
1answer
420 views

What is the difference between a forest and a spanning forest?

If a graph is labelled as a forest it does not contain any cycles, meaning it consists of all trees, which I realize can even be a single node (since that is technically a tree). If a graph is ...
2
votes
2answers
68 views

Construction Types or Type Constructions?

In any (simple) type theory there are base types (i.e. the type of individuals and the type of propositions) and type builders (i.e. $\rightarrow$, which takes two types $t,t'$ and yields the type of ...
2
votes
1answer
238 views

questions about binary search tree

Show that every n-node binary search tree is not equally likely (assuming items are inserted in random order), and that balanced trees are more probable than straight-line trees. How is it prove ...
2
votes
2answers
63 views

Embedding of Tree

Q. Proof for every Tree can be embedded into the plane. Conditions. We cannot use Euler Formula for Planar Graphs. We can use definition of tree, $V-E=1$, no-cycles, every edge is critical, there ...
2
votes
1answer
95 views

Proof of the Converse of Kraft's Theorem

So I have already proven Kraft's theorem for ternary trees, and I have been tasked with proving the converse. That is, I need to show that there is a ternary tree with $k$ leaves, such that leaf $i$ ...
2
votes
1answer
187 views

Probability of passing through 3 specific nodes along a binomial tree

Consider a re-combining binomial tree with probability of up = $p$ and probability of down = $(1-p)$. Let $n$ be the number of time steps in the binomial tree (the $x$-axis is time, and each column of ...
2
votes
1answer
170 views

Finite Rooted Binary Trees

I am new to learning about finite rooted binary trees. This lemma below is from John Meiers book: Groups, Graphs and Trees. There is no aval proof in the book. I was just wondering is I could catch a ...
2
votes
1answer
823 views

Oriented trees and ordered trees

I have this confusion regarding ordered and oriented trees. I know they are both rooted and in ordered trees, the order is important. So lets say I have four nodes 1,2,3,4 then it is given that the ...