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
33 views

Prove that minimum spanning tree is a tree

From the the Wikipedia page Minimum spanning tree: A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total ...
2
votes
0answers
118 views

Bounding the global intersection of a family of sets

Suppose that we have a decision tree of height $r + 1$ that describes how to increment an $n$-bit integer in the range $[0, 2^n -1]$. That is, the internal nodes are labelled with a bit position that ...
1
vote
1answer
23 views

Set of edges not contained in any spanning tree

The question is as follows: Prove that in a graph $G$ a set of edges $X$ which is not contained in any spanning tree is a cycle (or possibly an edge disjoint union of cycles). My thoughts: Proceed by ...
0
votes
1answer
31 views

Minimum spanning tree edge count

Given is a weighted complete graph where every weigth is a positive ineger. Let n be the amount of vertices. I have to prove that the number of edges of a minimum spanning tree of that graph is equal ...
-1
votes
1answer
125 views

Number of paths from root to a node in a tree

How to prove inductively the total number of paths from the root to all leaves in a given tree? From what I understand, one should show how to find the number of paths to a specific leaf, then use ...
1
vote
1answer
42 views

Finding Minimum Weight Subgraph Spanning Tree

Suppose we have a graph $G = (V, E, w:e\in E \to x \in \{0,1\})$. That is, a set of vertices, a set of edges and a weight function that assigns edges weights of 0 or 1. Suppose we also have a subset ...
0
votes
1answer
55 views

Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree.

Given the postorder sequence 1, 2, 3, 0, 7, 9, 8, 6, 5, 4 of the keys of nodes in a binary search tree, find that tree. I think i've done this right but i'm not sure.
0
votes
0answers
13 views

Minimum(maximum) cost of a weighted uni-height tree

If we have a rooted tree with all trunks the same height, and every vertex assigned a weight, is there a simple method to find the route from root to a leaf with minimum(maximum) cost?
0
votes
1answer
87 views

Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8

Question: Show the binary search tree that results from inserting elements 10, 14, 11, 9, 4, 2, 12, 16, 7, 5, 8 (in that order) into an (initially) empty binary search tree. Show also ...
0
votes
2answers
75 views

Tree. Number of nodes and children

Suppose a given tree $T$ has $n_1$ nodes that have $1$ child, $n_2$ nodes that have $2$ children, . . . , $n_m$ nodes that have $m$ children and no node has more than $m$ children, how many nodes have ...
1
vote
1answer
28 views

Using Euler's theorem to calculate the number of edges in a graph

I want to use Euler’s theorem for planar graphs to proof that for a tree $T = (V, E)$ that $|V | = |E| + 1$. Now It's very obvious that a tree is a planar graph since it is connected and there is no ...
1
vote
1answer
288 views

The number of pendant vertices in a tree

Let $T$ be a tree with vertices $\{v_1, v_2, . . . , v_n \}$ for $n \geq 2$. Prove that the number of pendant vertices in $T$ is equal to $$\large{2 + \sum_{v_i,deg(v_i) \geq 3}\big( deg(v_i) - 2 ...
1
vote
0answers
29 views
0
votes
1answer
19 views

Remove the root from a binomial tree

I have a binomial tree with height k. How do I proof that when I remove the root, the result will be k new binomial trees, each with with a height from 0 to k-1. Thanks in advance.
1
vote
1answer
119 views

Spanning trees of ladder graphs…

a. Draw the 1-ladder, 2-ladder, and 3-ladder graphs, and calculate the number of spanning trees for each. - I have completed this part and wanted to confirm that these numbers look accurate, I feel ...
2
votes
0answers
26 views

Maximum number of subtree in a spanning tree

Is it possible to determine the theoretical maximum of number of subtree that can be extracted from a spanning tree? Some context (I don't know whether this is useful): I build the spanning tree by ...
0
votes
1answer
26 views

Balance factor changes after local rotations in AVL tree

I try to understand balance factors change after local rotations in AVL trees. Given the rotate_left operation: ...
0
votes
0answers
45 views

Bottleneck distances for the Steiner problem in graphs

I have been reading the paper "Preprocessing the Steiner Problem in Graphs" by Duin (http://link.springer.com/chapter/10.1007%2F978-1-4757-3171-2_10) and I am having a bit of trouble wrapping my head ...
0
votes
0answers
8 views

Tree decomposition (Citation needed)

Recently, I read the statement "Fix $k\geq 1$, Any tree with at least $k$ edges may be decomposed as a union of edge-disjoint subtrees, each having between $k$ and $3k$ edges" Now I was wondering ...
1
vote
2answers
71 views

Number of reachable vertices in a tree

Given a tree $T$ with infinite nodes. Each node of the tree has exactly $C$ children. I need to figure out that, starting from a node at distance $h$ from root, how many distinct vertices can be ...
1
vote
2answers
34 views

Find all possible topological-sortings of graph G

A topological ordering of G is an ordering of the nodes as $v_1,v_2,...,v_n$ so that all edges point "forward": for every edge $(v_i,v_j)$, we have $i<j$. Moreover, the first node in a ...
0
votes
2answers
98 views

Trees with no vertex of degree 2 have more leaves than internal nodes

There is a question asked by portal about Tree having no vertex of degree 2 has more leaves than internal nodes so we want to prove this claim by induction and an answer from Micheal Biro suggested ...
1
vote
1answer
84 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 ...
1
vote
1answer
39 views

How can I draw a tree to represent combinations?

I understand how to systematically draw a tree for permutations. How do you do this for combinations? In my book, I don't see a system to avoid repetitions. I'd like to draw a tree of 5C3 if possible. ...
1
vote
1answer
37 views

Circuits and Trees

Given a graph G, can it be split into 2 sets of graphs($ G_1, \; G_2 $) such that, $G_1$ consists only trees and $G_2$ consists only circuits ? In other words: Is it possible to construct any graph ...
3
votes
1answer
253 views

Tree having no vertex of degree 2 has more leaves than internal nodes

If $T$ is a tree having no vertex of degree 2, then $T$ has more leaves than internal nodes. Prove this claim by a) induction, b) by considering the average degree and using the handshaking lemma. ...
0
votes
1answer
23 views

There are at least 22 vertex-disjoint paths between every pair of vertices?

$G$ is a graph on $n$ vertices and $2n−2$ edges$.$ The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for $G?$ For every subset of $k$ ...
0
votes
1answer
28 views

Intersection of all possible spanning trees of a connected, simple graph.

Is the intersection of all possible spanning trees of a simple, connected graph $G$ equal to the graph $(V_{G}, \varnothing)$? I'm not sure if this is a trivial question or not. Although I'm going to ...
4
votes
0answers
69 views

Why is the intersection of countably many homogeneously Suslin subsets of $\,^{\omega} \omega$ homogeneously Suslin?

I found this assertion in these notes: The derived model theorem (Steel) right in the beginning on page 3, together with the remark that this is 'not too hard to show'. Unfortunately, I'm ...
0
votes
1answer
120 views

Tree with no nodes of degree 2: prove that # leaves ># internal nodes using average degree and handshake lemma

Im really struggling to formalise my thoughts on this one. Basically I understand that if we would allow nodes with degree 2, then we could chain together infinitely many nodes to always produce ...
2
votes
1answer
26 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 ...
1
vote
0answers
33 views

Complexity analysis of alpha beta pruning of a full tree

I am trying to understand the derivation of a time complexity for an alpha-beta pruning algorithm but up till now have not found any reasonable recourse. Many recourses claim that if you take a full ...
1
vote
0answers
21 views

Yet another curious convolution

Some time ago, I found the following algorithmic problema: Count the number of distinct unrooted, unordered, labeled trees of $n$ nodes where each node has at most $k$ neighbors. Given that the ...
0
votes
0answers
82 views

For a k-ary tree with height h, the upper bound for the maximum number of leaves is $k^h$

i want to prove For a k-ary tree with height h, the upper bound for the maximum number of leaves is $k^h$. (assume the complete k-ary tree is a tree that is complete in all levels including the ...
0
votes
0answers
20 views

directed trees versus singly-connected directed graphs

According to wikipedia, a singly connected directed graph (a.k.a. Polytree) is a Directed Acyclic Graph whose underling undirected graph is a tree. How is this different from directed trees (trees ...
1
vote
0answers
41 views

Is there a name for this particular kind of tree graph?

I've recently encountered a problem which heavily involves analysis of structures analogous to weighted trees with no nodes of degree two (such a node along with its adjacent edges would be ...
1
vote
0answers
32 views

Binary Minimum Spanning Tree (from complete graph)

Given a weighted complete graph (or more exactly, a matrix of pairwise metric distances between vertices), I need to find a good approximation of the binary spanning tree of lowest total cost. There ...
3
votes
2answers
186 views

Graph Theory: Trees, leaves and cycles

So, a vertex is called a leaf if it connected to only one edge. a) Show that a tree with at least one edge has at least 2 leaves. b) Assume that G = (V, E) is a graph, V ≠ Ø, where every vertex ...
0
votes
1answer
78 views

Counting spanning trees and hamiltonian paths

Assumption : For any connected graph, every hamiltonian path is a spanning tree but not the other way around. If the assumption is wrong there is no need of reading any furhter. So is the assumption ...
0
votes
0answers
54 views

Extract the overall “structure” (“backbone”) of a set of vertices…

My main problem is that I am struggling to find a good graph-theoretical formulation of my problem, let alone a formal name for it (if it already exists, as I suspect it should)… Informally, given a ...
1
vote
0answers
21 views

Name of operation: changing the root of a rooted tree

What is (if any) the name of the operation of changing the root of a rooted tree? Picking a vertex which is not the root, then reorienting the edges in such a way that the vertex becomes the root?
0
votes
0answers
26 views

is the Root of a binary Tree counted as a node

I am working on this Homework questions and there's one thing I can't seem to understand. We are trying to proof using structural induction that some elements in T hold for the following statement ...
0
votes
0answers
19 views

Questions about this type of problem

Problem Consider the general chip-and-be-conquered recurrence relation: $T(n) = b_1T(n - 1) + b_2T(n - 2) + ... + b_kT(n - k) + f(n)$; for $n >= k$ for some constant $k >= 2$. The ...
0
votes
1answer
44 views

How would one go about solving these types of problems?

I'm totally lost. All I know is it has to do with binary trees and may need to be solved using induction. Show that every 2-tree with $n$ internal nodes has $n + 1$ external nodes. Show that the ...
0
votes
0answers
13 views

Terminology for excluded nodes

Given the following tree: A / \ / \ B C / \ \ / \ \ D E F / \ / \ G H Regarding node ...
0
votes
0answers
40 views

Is the following statement about tree true?

For a rooted tree T of oder n, what is the probability of that T contains a balanced tree of order 7? For example, there are total of 719 rooted trees of order 10, IF among all those 719 rooted trees, ...
0
votes
0answers
30 views

Defining a Nested Tree (set-theoretic)

I am new to the world of trees and I am trying to make a painless addition to this general definition: Let $X$ be a topological space and $\mathfrak{T}$ be a collection of sets. ...
0
votes
0answers
29 views

Perron vector of the distance matrix of a tree

Increasing properties of perron vector of distance matrix from the vertex corresponding to which row sum is minimum
0
votes
0answers
21 views

What is considered a unique homeomorphically irreducible tree?

Take, for example, this image that shows the possible trees of size 11 and this tree I created. Based on the 14 trees in the first image, how can I tell if mine is unique or not? Based on the shape ...
1
vote
1answer
61 views

Construction of rooted tree , please check whether my solution is correct?

Problem is A rooted tree with 12 nodes has its nodes numbered 1 to 12 in pre-order. When the tree is traversed in post-order, the nodes are visited in the order 3, 5, 4, 2, 7, 8, 6, 10, 11, 12, 9, ...