# Tagged Questions

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.

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 ...
70 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 ...
33 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 ...
93 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 ...
73 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 ...
35 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. ...
35 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 ...
224 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. ...
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$ ...
26 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 ...
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 ...
118 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 ...
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 ...
31 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 ...
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 ...
75 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 ...
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 ...
40 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 ...
30 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 ...
160 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 ...
73 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 ...
56 views

### What exactly is TREE(3)? [closed]

I've heard that it is an enormous number, but I honestly don't understand how someone gets to it. Could anyone explain it in layman's terms?
50 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 ...
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?
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 ...
19 views

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 ...
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 ...
13 views

### Terminology for excluded nodes

Given the following tree: A / \ / \ B C / \ \ / \ \ D E F / \ / \ G H Regarding node ...
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, ...
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. ...
27 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
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 ...
57 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, ...
26 views

### Any implementation of the Roskind-Tarjan algorithm for finding the maximum number of edge-disjoint spanning trees over a graph?

I am looking for an implementation of the Roskind-Tarjan algorithm [1] for finding the maximum number of edge-disjoint spanning trees over a graph. A Matlab implementation would be great. ...
40 views

### Probability tree diagrams

Exercice : True or false Let $E$ and $F$ be two events of an experiment. $$\mathbb{P}(E| \bar{F})=1-\mathbb{P}(E| F)$$ Solution : Flase due to the Law of total probability we've: ...
91 views

### Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T .

Find a recursive definition for inorder: binary Tree(T) → list(T ) where inorder(T ) is the list of nodes from an inorder traversal of T . I have no idea what this question is even asking me. What ...
102 views

### Number of spanning trees in a complete split graph

A graph is a complete split graph if we can partition it into an independent vertex set and a clique, such that every vertex of the independent vertex set is adjacent to every vertex in the clique. ...
25 views

### How many nodes in a K-ary tree with L leaf nodes

Assuming that we have a k-ary tree with L leaf nodes, can the average number of nodes in the tree be calculated if we were to know the average number of children for each node? If not, what other ...
67 views

### Dijkstra’s algorithm / path is this done correctly?

im doing this assignment and it seems as if my teacher has made a mistake. according to me in order to find the minimum spanning treee from a-z , you start from a and then go to : a,f,d,c,b,e,z,g ...
58 views

### Dijkstra's algorithm, am I or the teacher mistaken?

Imagine that Dijkstra’s algorithm has been used to show the length of the shortest path from $a$ to $g$ in the graph in figure 1. Which of the following vertices is added first to the set $S$? It's ...
65 views

### minimum number of leaves in a perfect binary tree

I'm trying to prove that the number of leaves in a perfect binary tree is at least H+1 where H is the height of the tree. This is what I've done up til now: No of leaves at height $H = 2^H$ Base ...
128 views

### Sum of roots of binary search trees of height $\le H$ with $N$ nodes

Consider all Binary Search Trees of height $\le H$ that can be created using the first $N$ natural numbers. Find the sum of the roots of those Binary Search Trees. For example, for $N$ = 3, $H$ = 3: ...
44 views

### Completeness in M-ary trees where the value of M is variable.

Definitions of complete trees are typically limited to some specific kind of tree, often an $m$-ary tree, where the number of children each internal node must have is a positive integer $m$. Consider ...
502 views

### Number of binary search trees on $n$ nodes of height up to $h$

How can I find the number of binary search trees up to a given height $h$, not including BSTs with height greater than $h$ for a given set of unique numbers $\{1, 2, 3, \ldots, n\}$? For example, if ...
47 views

### Binary tree node value by level

How can I calculate the value of given node level, for example: (let's use this image I found on Google Images and invert the level: starting at bottom 0..1..2..3..4) Knowing that each node pays ...
46 views

### $G=(V,E_1 \cup E_2)$ is a triangle free graph, where $G_1=(V,E_1)$ is planar and $G_2 = (V, E_2)$ is a tree. Prove that: $\chi (G) < 7$

can anyone help with this, any direction could be helpfull? I've tried using the fact that $G_1$ satisfies that it's planar and is triangle free because G is. So we should have $|E_1| \leq 2|V|-4$ ...
70 views

### Generating all coprime pairs

The Wikipedia article on coprime integers has a brief section on generating all coprime pairs. All pairs of positive coprime numbers $(m,n)$ (with $m>n$) can be arranged in two disjoint ...
53 views

### A tree has a root, leaves, and what?

The root of a tree is special, in that it has no parents. The leaves are special in that they have no children. The other nodes each have exactly one parent and more than zero children. Is there a ...
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 ...