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
0answers
81 views

Tree decomposition by hand for understanding

I am implementing "algorithm 2" from the paper "Treewidth computations I. Upper bounds" by Bodlander and Koster[1,page5] and I am not sure if I understand it or not. As I understand, the algoritm ...
2
votes
1answer
35 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 ...
1
vote
0answers
56 views

The number of edges in a tree is $n-1$

I am trying to prove that the number of edges in a tree is $n-1$ where $n$ is the number of vertices. I do not wish to use induction. I already have established that a tree is a planar graph. Now my ...
1
vote
0answers
32 views

How to determine size and height balance of binary search tree?

I've been reading/ learning binary search trees and I've been stuck on the following question for a while now. I have the following tree, how do I determine the height and size balance of it? How do ...
0
votes
1answer
63 views

What kind of tree it is? How to solve the problem?

I have a tree with following configuration: n is the number of different vertices v ($0 \lt v \le n$). Each vertice ...
2
votes
1answer
34 views

Finding a node in a full binary tree: expected number of comparisons

Consider a full binary search tree of height $k$ (the root is on level $1$ and the leaves on level $k$). By full I mean that all leaves are on level $k$ and level $k$ has exactly $2^{k-1}$ leaves. In ...
1
vote
1answer
70 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
33 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
65 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
18 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
196 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
50 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
139 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
262 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
56 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
48 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
63 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
39 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
0answers
13 views

Tranform a set of tree in a DAG

It is possible transform a set of directed tree into a DAG? in this way transform a set of tree in wich there are repeated nodes into a DAG where exist no pair of nodes repeated, in such a way these ...
0
votes
1answer
60 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
54 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
164 views

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 these 2 possible spanning trees cannot share the same edges, but ...
0
votes
0answers
48 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
51 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 ...
-1
votes
2answers
73 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
29 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
46 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 ...
5
votes
4answers
93 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
81 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
22 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
120 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
47 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
154 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
26 views

Adjacency of vertices from Prufer sequence

Is adjacency of vertices can be known from Prufer sequence without decoding? Thanks!
1
vote
1answer
13 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
37 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
80 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
88 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
135 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
1answer
139 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
25 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
86 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
108 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
2answers
63 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
1answer
152 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
70 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
102 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
114 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 ...
1
vote
2answers
322 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
55 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}$ ...