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

4
votes
0answers
50 views
+100

Pythagoras tree bounding size

The Pythagoras tree is a fractal generated by squares. For each square, two new smaller squares are constructed and connected by their corners to the original square. The angle of the triangle formed ...
2
votes
1answer
53 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 ...
6
votes
3answers
2k views

Spanning Trees of the Complete Graph minus an edge

I am studying Problem 43, Chapter 10 from A Walk Through Combinatorics by Miklos Bona, which reads... Let $A$ be the graph obtained from $K_{n}$ by deleting an edge. Find a formula for the number ...
1
vote
0answers
17 views

Number of ordinal trees (aka rose trees) with n nodes, of depth d, with l leaves

Is computing the number of ordinal trees (also known as "Rose trees") with $n$ nodes, of depth $d$, with $l$ leaves an open problem? I assumed at first that it was a known results but I could not ...
2
votes
0answers
124 views

A few questions about a relationship between some integer sequences and infinite recursive trees

In his book Gödel, Escher, Bach Douglas Hofstadter defines the following two integer sequences: Hofstadter G-sequence: $a(n)=n-a(a(n-1))$ Hofstadter H-sequence: $a(n)=n-a(a(a(n-1)))$ He says ...
0
votes
0answers
15 views

Terminology for property of two branches of a tree

Consider a tree $T$. A branch $B$ of a tree $T$ is just a proper subtree of $T$ (that is a subtree $B \subset T$ and $B \neq T$). Lets consider $B_1$ and $B_2$, two branches of a tree such that $B_1$ ...
1
vote
1answer
31 views

Find total number of ways to disconnect the following graph

Find total number of ways to disconnect the following graph: $4$ $5$ $6$ $8$ My attempt: I've done manually to find possible disconnected sets of given graph. I guess it is should be ...
1
vote
2answers
624 views

Prove through structural induction that a binary tree has an odd number of nodes

A full binary tree is a binary tree where every node has either 0 or 2 children. Prove that every non-empty full binary tree has an odd number of nodes. I dont know how to get started with this ...
0
votes
0answers
34 views

Assume that $|V | = |E| + 1$ and that $G$ is connected. Prove $G$ is a tree. [duplicate]

Let $G = (V, E)$ be a finite graph. (A) Assume that $|V | = |E| + 1$ and that $G$ is connected. Prove $G$ is a tree. (B) Assume that $|V | = |E| + 1$. Find an example that $G$ is not a tree.
1
vote
0answers
20 views

Enumerate out-trees that include a set of nodes in a directed graph

Given a digraph A, and an N set of nodes in the digraph. I need to enumerate the set of out-trees that contain those nodes. Where all the the out-trees leaves terminate on a node in set N. As a ...
0
votes
0answers
13 views

Algorithm for finding all maximum out-trees in a digraph

If we have a directed graph, and the graph contains subgraphs which are out-trees. We could find the set of out-trees, such that it does not contain any out-tree that is contained by another out-tree. ...
1
vote
2answers
513 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 ...
0
votes
0answers
12 views

KD-Tree implementation with lat/lon coordinates

I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct ...
3
votes
0answers
80 views

Existence of $\lambda^+$ Aronszajn trees when $\lambda$ is regular and $2^{<\lambda}=\lambda$

While I was dealing with Aronszajn trees I found the following exercise from Kunen's old book. If $\kappa=\lambda^+$ and $\lambda$ is a regular uncountable cardinal and $2^{<\lambda}=\lambda$ ...
1
vote
1answer
22 views

Which of the following is NOT true for $G$?

$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$ ...
4
votes
2answers
5k views

Finding number of homeomorphically irreducible trees of degree N

There is a scene in Goodwill Hunting where professor challenges students with task of finding all homeomorphically irreducible trees of degree 10. This is discussed in many places, such as here and is ...
0
votes
1answer
24 views

In Graph to tree: name of operation where edges removed and vertex/edge additions?

The graph has tree paths IN-1-OUT, IN-2-OUT and IN-3&4-OUT between IN and OUT in the left. I want to make each path to a branch like the right. What is the name of this operation or the name ...
0
votes
1answer
16 views

Binary Heap Question interpretation

In the question in the link below, how do I tell weather to draw out a binary min heap or a binary max heap? Am I misunderstanding the question? Binary Heap Question
1
vote
1answer
46 views

How to generate (recursively?) all non-isomorphic trees with 2 types of vertex labels with degree restrictions?

I am not sure if the title makes a whole lot of sense, but what I am trying to do is generate all non-isomorphic trees that obey the following: 1) Each vertex (including leaves) has one of two labels ...
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 ...
1
vote
1answer
25 views

Fundamental group of cylinder -triangulation method

Is this correct? Can we conclude that the fundamental group is trivial since there are no remaining generators on 1-simplices?
0
votes
1answer
17 views

Fundamental group Klein Bottle triangulation

I have been trying to find the FG of the Klein bottle, and I was wondering if someone could verify that this process is correct. After triangulating it, I then found a maximal tree (shown in yellow) ...
0
votes
1answer
36 views

Fundamental group of the sphere via triangulation

I know that the fundamental group of the sphere is zero, i.e. $\pi(S^2)=0$ I want to show this by triangulation, i.e: Triangulate the sphere Draw maximal tree Draw maximal contractable subspace ...
0
votes
1answer
40 views

Fundamental group of a tree?

Find the fundamental group of the space $C(T)=\{(x,y) \in T \times T \mid x\neq y\}$. $C(T)=\{(x,y) \in T \times T \mid x\neq y\}$ where $T$ is a graph $T$ is the graph made of $3$ edges with a ...
1
vote
1answer
545 views

Binary Tree and Overhead fraction Caluculation

Find the overhead fraction (the ratio of data space over total space) for each of the following binary tree implementations on n nodes: 2) Only leaf nodes store data; internal nodes store two child ...
1
vote
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 ...
4
votes
0answers
245 views

Number of Spanning Arborescences

I am trying to prove the following result from my book: Let $G$ be a directed graph with vertices $x_1,x_2,\dotsc, x_n$ for which a directed Eulerian circuit exists. A spanning arborescence ...
3
votes
1answer
32 views

Best way to find if a subgraph has a cycle

I am implementing Kruskal's algorithm to find a minimal spanning tree of a connected graph $G$. If $H$ is a subtree of $G$, does anyone know a smart way of checking if $H+e$, where $e$ is an edge of ...
0
votes
1answer
419 views

Min and max height of a binary tree

Suppose I have n nodes, how can I find the max and min height of a tree? I've seen varying statements for the min height such as log2 (n) and log2 (n+1) but I wasn't sure which was correct and I am ...
0
votes
0answers
9 views

Minimum spanning trees

Let $G = (V,E)$ be an directed connected graph with $|E|>1$, $w:E→R$ be an edge-weight function and $k∈{1,2,...,|E|-1}$. Sort the edge in E as $e_1,e_2,...,e_|E|$, such that $w(e_1) \leq w(e_2) ...
0
votes
5answers
56 views

Prove by induction: A tree on n≥2 vertices has ≥2 leaves

This is what I have. I'm pretty sure this is quite incorrect, but am I at least headed in the right direction? Base Case: $P(2)$: Tree on 2 vertices can only have one edge, the edge connecting the ...
0
votes
2answers
32 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
2
votes
1answer
411 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 ...
5
votes
2answers
136 views

Maps of primitive vectors and Conway's river, has anyone built this in SAGE?

I am attempting to teach number theory from John Stillwell's Elements of Number Theory in the upcoming semester. There are two sections (5.7 and 5.8) which describe the diagrammatic method for the ...
0
votes
0answers
24 views

Is the path from u to v is diameter of the tree?

The diameter of a tree is the longest (simple) path in the tree. Let u be a vertex in a tree and let v be the farthest from u vertex in T. Show that the path from u to v may not be a diameter I am ...
0
votes
0answers
16 views

Minimal spanning trees in multigraphs with constraints

I have a multigraph G whose edges have three identities. Let's say I have three colors of the edges red, blue and green and each two nodes may be connected by a red, blue and/or green edges. The graph ...
0
votes
1answer
30 views

Is there an efficient algorithm to find all the maximum matching in any tree?

A matching in a graph (G) is a set of mutually non-adjacent edges of (G). A maximum matching is a matching maxima cardinallity. A tree is an acyclic connected graph. Is there an efficient algorithm ...
1
vote
3answers
285 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 ...
0
votes
0answers
12 views

Minimum number of pages in a B-Tree of order n?

How can I calculate the minimum number of pages in a B tree of order n and height 3? 1st level = 1 page 2nd level = 2n+1 pages 3rd level = ? 3rd level is 1? Or how many pages?
0
votes
1answer
18 views

Completion of acyclic sub graph

Statement: Given an acyclic subgraph of a connected graph, show that this subgraph can be completed into a spanning tree of the graph. I know that there is a theorem that states that any connected ...
0
votes
2answers
46 views

Difference between Depth first search and Breadth first search algorithm

Currently I am studying Depth first search algorithm and Breadth first search algorithm. Both these algorithms are looking quite similar to me except for some differences. In BFS, we start with a ...
0
votes
0answers
14 views

Minimum Path Cover in Trees

We have a Tree with $m$ nodes and $m-1$ edges. We are given $Q$ queries. Each query consists of a list of nodes of size $k$, $[n_1, n_2, ..., n_k]$. I need to answer the minimum number of paths that ...
0
votes
0answers
20 views

Nodes lying on Same Path in Trees

Given a Treen with $n$ nodes and $n-1$ edges, I have to answer $Q$ queries. In every query, I get a list of nodes of size $k$, $n_1, n_2, ..., n_k$. I need to answer the minimum number of paths that ...
7
votes
2answers
889 views

Is the graceful labeling conjecture still unsolved?

From the Wikipedia article on graceful labeling: ... A major unproven conjecture in graph theory is the Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that ...
0
votes
1answer
17 views

Binary Decision Trees

I know the basics to a binary decision tree, but this problem has me a little stumped, and I'm looking for some verification on my ideas. The problem is: "Create a binary decision tree that reflects ...
0
votes
1answer
28 views

Constructing a computably infinite tree with no computable infinite branches using PA

Define an infinite tree as any set of sequences closed under prefix restriction, i.e. any prefix restriction of a sequence in the set is also in the set, where a prefix restriction is a restritcion of ...
0
votes
1answer
30 views

Show that in a binary tree, if B is the number of branch points (including the root) and L is the number of leaves, then one has the relation L = 1+B

We have been discussing trees lately, but have yet to even touch on the topic of a binary tree. I understand what a leaf is, but we didn't have one for the term "branch points" Without being 100% sure ...
-1
votes
1answer
44 views

How to prove that each edge of tree is a bridge?

How to prove that each edge of tree is a bridge? My attempt: Tree is a connected graph which has no cycle, and in a connected graph, bridge is a edge whose removal disconnects the graph. Let ...
2
votes
1answer
26 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) ...
0
votes
0answers
17 views

Minimum biconnected graph from spanning tree algorithm

I'm thinking about if there exist an algorithm, which can build a biconnected graph from spanning tree? The problem is that it should be minimal-weight (each edge between every pair of nodes has it ...