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
2answers
814 views

graph theory and forests

We were given an this question in my class: Prove that a forest with n vertices and m components has n-m edges using induction on m. Induction is not my strongest point and I was wondering if anyone ...
1
vote
1answer
69 views

Looking to generalize a binomial tree with some constraints.

I've got a set of sample data and I'm looking to see if it's possible to generalize a binomial formula to give a closed form solution to this. If not, would it be possible to write a program to do ...
1
vote
1answer
607 views

Prove that in every tree, any two paths with maximum length have a node in common.

Prove that in every tree, any two paths with maximum length have a node in common. This is not true if we consider two maximal (i.e. non-extendable) paths. What does this even mean?
1
vote
1answer
555 views

Number of possible Prüfer codes

I am trying to solve the following problem in my book: (Code stands for Prüfer code) Consider labelled trivalent rooted trees $T$ with $2n$ vertices, counting the root labeled $2n$. The labels are ...
1
vote
1answer
6k views

Maximum number of distinct binary tree possible with 4 nodes

what is the maximum number of distinct binary tree is possible with 4 nodes? ans is 6 but how? acc to me it should be 14
1
vote
3answers
106 views

Comparison trees

You have 60 coins. You know that 1 coin is either lighter or heavier than the other coins. How many comparisons are needed in a worst case scenario to discover which coin is the false one and ...
1
vote
1answer
22 views

Need combinatorial formula

Let we have a forest $F_n(P)$ with $n$ nodes defined by set $P$ of all pairs $\{\text{father}, \text{son}\}$. For instance $P=\{\{1, 2\}, \{3, 4 \}, \{1, 3 \}\}$ defines a forest $F_5(P).$ Let ...
1
vote
0answers
22 views

Kelly's Proof Of Reconstruction Conjecture For Trees

The vertex reconstruction conjecture states that a graph on n>2 vertices can be discovered from only knowing its proper induced subgraphs. Kelly proved this for trees in 1961. I saw his proof and I ...
1
vote
0answers
22 views

Prove that a connected graph with $n$ vertices is a tree iff it has $n-1$ edges. [duplicate]

What are different ways of proving this theorem, using different definitions for a tree (e.g. maximally acyclic graph, minimally connected graph, there's a unique path between any two vertices, etc.)
1
vote
0answers
24 views

Prove by induction a property of a tree graph

Prove by induction (and without the use of cycle definition) that if to delete a leaf vertex from a tree graph it will stay as a tree graph. I think Ive got it wrong but what I did is the following: ...
1
vote
1answer
57 views

$G’$ be the graph constructed by squaring the weights of edges in $G$.

Let $G$ be a weighted graph with edge weights greater than one and $G’$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T’$ be the minimum spanning trees of $G$ and ...
1
vote
1answer
24 views

prooving graph with no cycles and |V | = |E| + 1 is a tree.

My assignment is to prove that G = (V, E) is a tree if and only if |V | = |E| + 1 and G has no cycles. However, I am having some trouble doing just that. We defined a tree as a graph which is ...
1
vote
0answers
48 views

Graph Theory: Are Infinite Trees Planar?

Graph theory: Are infinite trees planar? I think countable trees are, but not uncountably infinite trees, apparently. How does one construct such a tree?
1
vote
1answer
21 views

Upperbound in the number of spanning trees of a r-regular Graph

i was trying to proof this upper bound in the number of spanning trees $t(G)$ of an r-regular graph G (and discuss what happens with equality) $t(G)$ $\leq$ $\frac{1}{n}$$(\frac{rn}{n-1})^{n-1}$ ...
1
vote
1answer
41 views

Encoding the answers to questions somewhere in a binary tree

I have a sequence of binary questions $(U_1,\dots, U_N)$ with some distribution. I know the answer to $n\leq N$ (mod-)adjacent questions, and want to convey this knowledge with as few bits as ...
1
vote
1answer
78 views

Build Tree by Prüfer Code $(6,2,2,6,2,5,10,9,9)$

I have the Prufer Code $(6,2,2,6,2,5,10,9,9)$. I want to build the corresponding tree. My algorithm: 1) Tree = $\{\}$, code = $(6,2,2,6,2,5,10,9,9)$, count = $(1,2,3,4,5,6,7,8,9,10,11)$ 2) Tree ...
1
vote
1answer
34 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 ...
1
vote
0answers
25 views
1
vote
1answer
98 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 ...
1
vote
2answers
60 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
1answer
22 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 ...
1
vote
0answers
20 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 ...
1
vote
0answers
34 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
25 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 ...
1
vote
0answers
53 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?
1
vote
0answers
39 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 ...
1
vote
2answers
438 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 ...
1
vote
0answers
45 views

How to mathematically judge if there is a spanning tree in a graph?

Given a graph $G=(V,E,A)$ where $V$ is the set of the vertices, and $E$ is the set of sides, and $A$ is the adjacency matrix of dimension $n\times n$. $G$ is undirected or directed. We define the ...
1
vote
0answers
21 views

All possible depth first spanning trees of a directed graph.

I am looking for an algorithm that generates all possible depth first spanning trees of a directed graph that has a known root.
1
vote
1answer
95 views

Maximum nodes in AVL tree with distinct positive integers

Assuming that all keys in an AVL tree are distinct positive integers. Suppose that the root node of an AVL tree T holds the key N. What can be estimated largest possible number of nodes in T ? We ...
1
vote
0answers
40 views

Is there a polynomial time algorithm for Poly-trees (oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far). What about Poly-trees (oriented trees)? These are DAG's ...
1
vote
0answers
43 views

Existence of increasing pair of labeled trees in an infinite sequence

Assume labeled rooted trees with labels from a fixed set $\{1\ldots m\}$. For a tree $T$, we have: $V(T)$ the set of vertexes, $root(T)$ the root of the tree, $l_T: V(T)\rightarrow \{1\ldots m\}$ ...
1
vote
1answer
63 views

Is my graph a tree?

Let M be a smooth connected manifold. G is a group act on M cocompactly and suppose there is a harmonic function $h$ on M with minimal energy.$h:\rightarrow [0,1]$ such that h is nonconstant and ...
1
vote
1answer
44 views

No. of Comparisons to find maximum in $n$ Numbers

Given $n$ numbers, we want to find the maximum. In order to find the maximum in a minimal amount of comparisons, we define a binary tree s.t. we compare $n'_1=\max(n_1,n_2)$, $n'_2=\max(n_3,n_4)$; ...
1
vote
1answer
52 views

Prove number of edges in an edge-disjoint spanning tree

I have the following problem. It isn't homework--it's additional work I want to do to further grasp the material in my Combinatorics class. Show that if a graph $G$ contains $k$ edge-disjoint ...
1
vote
0answers
83 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
71 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 ...
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 ...
1
vote
1answer
73 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
0answers
53 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 ...
1
vote
0answers
31 views

Adjacency of vertices from Prufer sequence

Is adjacency of vertices can be known from Prufer sequence without decoding? Thanks!
1
vote
1answer
57 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) ) ...
1
vote
0answers
146 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 ...
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 ...
1
vote
1answer
198 views

Discrete math - Prove that a tree with n nodes must have exactly n - 1 edges? [duplicate]

I'm new in discrete math. Can someone prove simply that a tree with $n$ nodes must have exactly $n - 1$ edges. I have researched the solution but I haven't founded yet. I know of course, a tree with n ...
1
vote
0answers
53 views

Expected Max Pseudotree Size

I'm working on a problem where I need to calculate the expected maximum pseudotree size in a randomly-generated pseudoforest with $n$ nodes. Expected maximum value is of course: $$ E(x) = ...
1
vote
1answer
117 views

Spectrum of infinite d-regular tree

Consider the adjacency matrix of the infinite d-regular tree, call it A. To find the spectrum we consider it as an operator in $L^2(V)$. It is stated that $A-\lambda I$ is always one-to-one. I do ...
1
vote
1answer
47 views

Graph theory, trees, show T is subgraph of G

Let T be a tree with n vertices. G be a non-empty graph with $\delta$(G) $\ge$ n-1. Prove that T is a subgraph of G. If it's a tree then I know it has to be connected and if the minimum degree is ...
1
vote
0answers
32 views

Calculate the total cost

According to my notes: $$T(n)=T\left(\frac{n}{2} \right)+T\left(\frac{n}{4} \right)+T\left(\frac{n}{8} \right)+n$$ Th recursion tree is this: Cost per level $i \to \left( \frac{7}{8} ...
1
vote
1answer
123 views

Partitioning a planar graph into spanning trees?

Suppose I have a simple, planar graph, which I want to partition into three edge sets such that each set forms a spanning tree. I've made an attempt at a solution, but it requires a few assumptions ...