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

1
vote
1answer
247 views

Sentences, Formal Grammars with derivation (parse) trees

I've been reading / studying formal grammars for the past few weeks and I came across a question that puzzled me and I cannot seem to get my head around it for some reason. ...
0
votes
1answer
47 views

Directed spanning tree

Consider a directed graph. Is there any theorem on minimum number of outgoing or incoming links for each node of digraph that guarantees the existence of directed spanning tree?
1
vote
2answers
67 views

Shortest Path on Specific Graph with one Property !?

I stuck in one challenging question, I read on my notes. An undirected, weighted, connected graph $G$, (with no negative weights and with all weights distinct) is given. We know that, in this ...
0
votes
0answers
28 views

Tree structure by using integer markers

I'm trying to model a situation in witch a group of entities are organized hierarchically. We say that entity A has privileges over entity B if there a direct hierarchical connection between A and B ...
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
103 views

Graph Theory: labelled tree

I am preparing for the final exam, but struggling with these questions. How many labelled trees with $2n$ vertices such that the vertex with label $1$ has degree $k$, for $k = 1, 2$ and $n$? Also, A ...
2
votes
1answer
222 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 ...
0
votes
0answers
1k views

Modifying Kruskal's algorithm for Maximum Spanning Tree

So in our class, we did a proof on Kruskal's algorithm for finding Minimum Spanning Tree. Now, based on that, I have to modify it to find me a Maximum Spanning Tree. I know the idea, taking ...
1
vote
1answer
79 views

Collection of spanning trees for a simple connected graph

Consider a graph $G$ whose edges are labelled $\{1, 2, ..., k\}$. Then the set of spanning trees is a collection of subsets of $[k]$. a) Let $T$ = $\{\{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}\}$. Can $T$ be ...
1
vote
1answer
65 views

Tree-related problem, counting leafs

I am studying Graph Theory right now, and I have solved tons of problems so far. However, I got a tree-related problem, where it asks me to prove that a tree, in which maximum node degree is 6, the ...
3
votes
1answer
107 views

Proofs involving some general formulae for trees and binary trees.

So here I have 3 tree-related questions. 1) Let $n\geq2$ and let $d_1 ≤d_2 ≤···≤d_n$ be a sequence of integers. Show that there is a tree with degree sequence $d_1,d_2,...,d_n \Leftrightarrow \sum ...
1
vote
0answers
66 views

Traversing multi-way tree, computational complexity

This is a computational challenge. I am looking for a clever simplification or heuristic. Imagine a multi-way tree. Each node has three child branches. Consider them to be decisions; do A, do B, do ...
0
votes
1answer
221 views

Proof verification: Prove that a tree with n vertices has n-1 edges

This question is not a duplicate of the other questions of this time. I want to ask is how strong is the following proof that I am going to give from an examination point of view? Proof: Consider a ...
0
votes
1answer
267 views

Prove graph cannot have exactly two distinct spanning trees [closed]

Prove that a graph cannot have EXACTLY two distinct spanning trees.
1
vote
1answer
444 views

Prove that a graph cannot have two distinct spanning trees

Prove that a graph cannot have two distinct spanning trees. I'm confused with this proof. More so that I think I'm confused as what distinct in this context means? Initially I thought it was that ...
0
votes
0answers
58 views

How to tell if a directed graph has a cycle?

If I have the directed graph here: I am confused whether or not this is a cycle or not. Because in the underlying graph, this is a 3-cycle for sure, but in the directed graph, there is no cycle if ...
3
votes
1answer
64 views

Number of spanning trees of a labeled graph

This labeled graph is given, I need to find the number of its spanning trees. The number of spanning trees of the following graph is 3 and the number of spanning trees of this is 8 So as a ...
0
votes
2answers
82 views

How many Hamiltonian cycles are there in $K_{10,10}$?

I want to calculate the number of Hamiltonian cycles in $K_{10,10}.$ Could anyone help me? I think in $K_{10}$ we have $9!$ Hamiltonian cycles.
1
vote
2answers
32 views

Trees-related proof

I just began my Graph Theory course, so I'm pretty knew in this area, at least when it's about formal proofs(I have some experience on intuitive level, implementing certain algorithms related to graph ...
1
vote
3answers
65 views

Traversing through a binary tree

Consider a full binary tree of n nodes numbered from 1 to n in the common top-down left-to-right manner. For the sake of the ...
6
votes
4answers
326 views

What is the number of full binary trees of height less than $h$

Given a integer $h$ What is $N(h)$ the number of full binary trees of height less than $h$? For example $N(0)=1,N(1)=2,N(2)=5, N(3)=21$(As pointed by TravisJ in his partial answer) I can't ...
2
votes
1answer
162 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 ...
0
votes
0answers
31 views

Determining whether two trees are isomorphic

Is there a (probably recursive) algorithm that can be used to determine whether two not necessarily binary ordered (sub)trees are isomorphic or not?
3
votes
2answers
340 views

Find a Generating Function for Ordered Rooted Ternary Trees

The Full Question If we let $T=$ the family of rooted ternary trees, $t_n =$ be number of trees in $T$ with $n$ nodes and $T(x) = \sum\limits_{n=0}^{\infty}w_nx^n$ be the generating function of $T$. ...
0
votes
0answers
82 views

Proving number of leaves in $m$-ary tree.

Prove that a full $m$-ary tree with $i$ internal vertices has $l=(m-1)i +1$ leaves. I'm having trouble finding any good information about $m$-ary trees online I've got a few pictures but they don't ...
0
votes
2answers
406 views

Number of labeled non-isomorphic trees on $n$ vertices

Is there any algorithm to build or count the labeled non-isomorphic trees on $n$ vertices ?
1
vote
0answers
32 views

Adjacency of vertices from Prufer sequence [closed]

Is adjacency of vertices can be known from Prufer sequence without decoding? Thanks!
1
vote
1answer
20 views

Get number of vertices when number of internal vertices is known ofr a full binary tree

But I can find a counter example: * / \ * * / \ / \ * * * * Here $k = 2$, but number of vertices is 6, and number of terminal ...
1
vote
1answer
63 views

Leftish Heap and Its Right Spine

Purely Functional Data Strutures presents the following question: Chapter 3, Question 1: "Prove that the right spine of a leftist heap of size n contains, at most, floor ( log ( n + 1) ) ...
2
votes
1answer
146 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
157 views

Prove that the vertex degree of a minimum spanning tree is in $\mathcal{O}(1)$

I have given a set of points $S$ in $\mathbb{R}^2$. From the this points I create a mininum spanning tree MST. The euclidean distance of the points is used as the weight for the edges. The ...
2
votes
1answer
199 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 = ...
3
votes
1answer
751 views

what is an “edge disjoint spanning tree”?

if there are n = 2 vertices in a connected graph, i am supposed to have "n/2 edge disjoint spanning trees". This means i should have 1 edge disjoint spanning tree for a n = 2 graph? My best guess ...
0
votes
1answer
38 views

Graph Theory: proof about the number of vertices in a Tree's component

I'm having some problem understanding the question below: Let T = (V,E) be a tree. Show that T has a vertex v such that for all e that exists in E, the component of T-e containing v has at least ...
1
vote
0answers
186 views

How to find the number of connected components of a graph by using its 16x16 adjacency matrix?

Good day, I have this exercice that provides me with the 16x16 matrix of adjacency of a graph and it asks me to find the number of connected components of the graph and I need to give a spanning tree ...
3
votes
0answers
127 views

Associativity of the tensor product of dendroidal sets

For any smal category $A$, I shall write $\widehat A$ for the category $[A^{\text op}, \mathbf{Set}]$ of presheaves on $A$, and $y_A\colon A \to \widehat A$ for the Yoneda embedding relative to $A$. ...
1
vote
3answers
276 views

Rooted Tree and Greedy Algorithms

In a Rooted Tree, we have a message on Root. in each step, each node that has a one copy of message, can transfer this message to at most one of it's childeren. we want to use minimum step and send ...
2
votes
2answers
388 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
0answers
90 views

Graph Algorithm and Cycle Detection

In $O(|V|+|E|)$, we can detect whether a Directed Graph has a cycle or not. ---> True In depth-first seach on DAG, there is no Back Edge. ---> True With known Number of Edges, in $O(|V|)$ and not ...
1
vote
1answer
257 views

Remove edge from tree, number of vertices

Prove that if $T$ is a tree on at least $k+1$ vertices and max degree at most $d$, then there exists an edge $e$ such that the removal of $e$ causes $T$ to split into two trees where at least one of ...
2
votes
3answers
210 views

In a Tree, show that the largest degree of a node <= number of nodes of degree 1

Let $T$ be a tree in which the largest degree of a node equals to $t$. Let $n_1$ denote the number of nodes of degree $1$ in $G$. Prove that $n_1 ≥ t$ I understand why this works but I am not sure ...
4
votes
4answers
989 views

In binary tree, number of nodes with two children when number of leaves is given

For a binary tree what is the number of nodes with two children when the number of leaves is 20? I know that for complete binary tree, when the number of leaves is x then the number of internal nodes ...
2
votes
0answers
101 views

Counting unlabeled and non-uniquely labeled trees

I recently learned about Cayley's formula, which states that the number of trees on $n$ labeled vertices is $n^{n-2}$. As I understand it, this works because we can prove that there are $n^{n-2}$ ...
0
votes
1answer
175 views

Prove by induction that every complete $k$-ary tree of depth $n$ has $(k^{n+1}–1)/(k-1)$ nodes for all integers $n\ge 0$, where $k\ge 2$.

A strictly $k$-ary tree is a $k$-ary tree (a binary tree is a $2$-ary tree) in which every node has either no children (is a leaf) or $k$ children. A complete $k$-ary tree of depth $n$ is a ...
0
votes
1answer
181 views

Huffman coding - conditions for perfect tree output

The question is: Given 4 characters and their frequencies, what's the max possible difference between the frequency of the rarest character and that of the most common character, so the output Huffman ...
2
votes
0answers
73 views

Examples of forcings which add no “definable” Aronjain tree

Maybe a bit board question but: Fixing a regular cardinal $\kappa$ in the ground model, I am looking for examples of set forcing notions which preserve regularity of $\kappa$ and add no new $\kappa$ ...
6
votes
7answers
458 views

EGF of rooted minimal directed acylic graph

I am trying to find the exponential generating function of directed minimal acyclic graphs (which I now call dag), where every non-leaf node has two outgoing edges. Context: A simple tree ...
0
votes
2answers
50 views

Binary search tree. Counting.

How many BSTrees can be constructed from given set: $\{1,2,3,4,5\}$? I have no idea how to solve it. Please help me. Thanks in advance.
1
vote
1answer
1k 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 ...
3
votes
1answer
58 views

Identifying Binary Search Trees from their Prufer Sequence

If you ignore its root, a Binary Search Tree generated by some permutation of $\{1, \ldots, n\}$ is a labeled tree. Which means you can calculate its Prufer Sequence. I did this in Python and I found ...