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

0
votes
1answer
464 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 ...
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 ...
3
votes
3answers
3k views

Number of binary trees with N nodes

I am trying to calculate the number of trees (non isomorphic) with n nodes (total including leaves). I think that there are n! such trees, but I don't know how to prove that. I know that the number ...
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
1answer
461 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
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 ...
0
votes
1answer
22 views

Proof of Mutually Inclusive Tree Properties

I don't know if that's the most accurate title. I'm trying to prove that one property of trees implies another without using any of the other properties. This is for homework. But I'm really just ...
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
1answer
314 views

Let $G$ be a connected graph, then $G$ is a tree iff $G$ has no cycles

Prove the following: Let $G$ be a connected graph, then $G$ is a tree $\iff$ $G$ has no cycles. $\Rightarrow$ If $G$ is connected and a tree then by the definition of tree it has no cycles. ...
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.)
0
votes
1answer
29 views

Depth first search tree in an undirected graph $G$.

Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$. which one of 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 ...
0
votes
1answer
20 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$ ...
6
votes
2answers
8k views

Determining Ambiguity in Context Free Grammars

What are some common ways to determine if a grammar is ambiguous or not? What are some common attributes that ambiguous grammars have? For example, consider the following Grammar G: $S \rightarrow ...
2
votes
1answer
39 views

Finding DFS in undirected graph

Consider the following sequence of nodes for the undirected graph given below. a b e f d g c a b e f c g d a d g e b c f a d b c g e f A Depth First Search (DFS) is started at node a. The nodes ...
0
votes
1answer
19 views

Are subgroups of automorphism groups of trees direct product of symmetric, cyclic and dihedral groups?

My question is triggered by my confusion with the notation $\Psi$ in Constructive Approach to Automorphism Groups of Planar Graphs by Klavík et al. The notation $\Psi$ was first used expressing ...
0
votes
0answers
15 views

How to find the best-case and average-case number of comparisons performed by a comparison tree?

So I'm reviewing some material before a midterm tomorrow and I came across this question: ...
2
votes
1answer
21 views

Find depth of three node tree

I am trying to write a formula to find the depth of a three node tree and having issues doing it. Each node will have an index number going from top to bottom, left to right. It will look something ...
0
votes
2answers
19 views

Given a forest, adding k edges would result in a cycle Proof

Assume you have a forest with k connected components. Prove that if you added $k$ edges, you would obtain a cycle. I’m thinking these facts/theorems may be useful... In a forest, each component ...
0
votes
1answer
15 views

What's the complexity class of Sub-Polytrees isomorphism?

In terms of Subgraph isomorphism I believe Directed Acyclic Graphs (DAG's) are in the np-complete complexity class. What about Poly-trees (oriented trees)? These are DAG's where the possible paths ...
0
votes
0answers
12 views

Possible paths in trinomial tree with recombination

So I know that the number of possible paths to end up in node $i$ from the top in a binomial tree with recombination at step $n$ is equal to $\binom{n-1}{i-1}$. Is there a similar formula for the ...
2
votes
1answer
22 views

Graphs embeddable into tree like simplicial 2-complexes

A tree gives rise to a simplicial 1-complex. A tree like simplicial 2-complex would be simplicial 2-complex without any closed 2-subcomplexes (the analog of a cycle in graphs) and such that the ...
2
votes
0answers
26 views

Applications of Prüfer sequence

Reading a book about a graph theory I found out about Prüfer's sequences which converts a labeled tree of $n$ vertices into an array of $n-2$ numbers. I was actually pretty surprised by this and was ...
3
votes
1answer
45 views

How many trees on N vertices have exactly k leaves?

I need help on the topic of counting labeled trees (with its nodes numbered from 1 to N) with exactly k leaves. I have thought about surjective functions that return the father of a node, but I'm not ...
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
19 views

Full 4-ary tree with 58 internal nodes

I'm not sure how to answer this question In a full 4-ary tree, there are 58 internal nodes. What is the number of leaf nodes in this tree? So a full 4-ary tree means every node has 0 or 4 ...
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: ...
0
votes
1answer
18 views

Prove by induction the number of edges in a tree given the leaves.

Define a cs130A tree to be a single leaf node or an internal node (the root) connected to two disjoint subtrees, which are themselves cs130A trees. Prove by induction that for all cs130A trees the ...
0
votes
0answers
23 views

How to find total node in tree

I wonder that how to generalize formula of tree. For example, let T be a tree and height of this tree "h" generated in a way that starting from the root node with h children, the branch factor ...
0
votes
0answers
18 views

Get sister node of all nodes given edge list

I've run into this problem writing some code to do some analyses on phylogenetic trees in Python. Let's say I have a tree: ...
1
vote
1answer
27 views

Algorithm for equality of trees of restricted depth

Are there any efficient algorithms to decide whether two trees of limited depth, where all nodes have a finite number of childs, are equal interpreted as finite sets with the leaves the "atomic" ...
0
votes
1answer
20 views

What is the amount of non-isomorphic trees of order n with a maximum incidence of 4?

It's a graph-theory model of the theoretical amount of possible non-cyclic alkanes isomers. I can't find a way to compute it? Any hints appreciated.
0
votes
1answer
106 views

Tree question proving [closed]

Let $T_1$ be a tree of height $h$ such that the root has one child, and the branching factor at each level is one more than the branching factor at the previous level. Thus, the root has one child, ...
0
votes
0answers
46 views

Can Collatz's problem be used as a pseudo random prime sieve?

If you take the concept of $3x+1$, $\dfrac{x}{2}$ and starting at 2, create a tree. On the left nodes you apply the $3x+1$. On the right nodes, if the parent node is even apply the $\dfrac{x}{2}$. ...
2
votes
1answer
404 views

Proof involving maximum weight of edge in minimum spanning tree

Let $G$ be a minimum spanning tree of a complete graph. Let $e$ be the maximum weight edge in $G$. I'd like to proof that given any other spanning tree $G'$ of this graph, being $j$ the maximum weight ...
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 ...
2
votes
2answers
67 views

In a full binary tree of depth $d$, what is the number of pairs of vertices at distance $t$ from each other?

I can come up with a dynamic-programming-type program to compute this number, but I am wondering if a nice closed form formula is known. By "full" I mean a binary tree where every vertex is within ...
0
votes
0answers
10 views

Proof by induction that $\sum \limits _{i=1} ^n d^{-l_i} = 1$ sentence in a full tree [duplicate]

How do I prove by induction that $\sum \limits _{i=1} ^n d^{-l_i} = 1$ where: $d$ = the number of children of each node; $n$ = the number of leaves; $l$ = the depth of each leaf $l_1, \ldots, l_n$? ...
0
votes
1answer
17 views

Every simple graph has at least $n-k$ edges.

From here on, $n$ will denote the number of vertices and $k$ will denote the number of connected components of the graph in question. Theorem. Let $F$ be a forest, then $F$ has $n-k$ edges. ...
0
votes
2answers
43 views

There are $n^{n-3}$ numbers of trees with named edges - how to proof?

How to proof that there are $$ n^{n-3} $$ trees with $n$ (unnamed) vertexes and $n-1$ named edges: $\left\{1, 2, 3, 4, ..., n-1\right\}$?
1
vote
1answer
128 views

Location of two “centers” in a tree

This problem came up during a recent (and already finished) coding competition on Hackerrank, I was wondering if someone stumbled upon a proof. [This question is my paraphrasing of the original] ...
0
votes
1answer
9 views

Finding a unique tree for given in order and postorder traversals

I just encountered a problem to find a tree for given inorder and postorder traversals.Can anybody elaborate the same using an example ?
1
vote
1answer
401 views

Prove that a graph cannot have two distinct spanning trees

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 ...
0
votes
0answers
46 views

A little bit more difficult problem regarding rooted plane trees

A question regarding rooted plane trees bothers me. We know that the number of rooted plane trees with $n$ nodes equals to $n-{th}$ Catalan number, that is $|Tn| = Cn$. But what is this number if we ...
0
votes
0answers
41 views

Help with functions of vertex sets

Let vertex sets $V_1$ and $V_2$ be defined by $V_1= \{1, 2, 3\}$ and $V_2 = \{a, b, c \}$. Let $E_1 = \{ \{ 1, 2\}, \{2, 3\} \}$, and let $E_2 = \{ \{a, b\}, \{b, c\} \}$ be the edge sets ...
0
votes
1answer
27 views

how can i Prove that by adding one edge to G you create a cycle in G?

Any one help me to show the prove for this? Let the undirected graph G = (V, E) be a tree. Prove that by adding one edge to G you create a cycle in G.
0
votes
2answers
23 views

an intuition for $\sum {\frac{(n-2)!}{k_1!k_2!…k_n!}}=n^{n-2}$

in studying about Graphs I've faced to the problem which says that the number of trees on n points is $n^{n-2}$. In the solution manual of the book the problem is reduced to the summation $\sum ...
0
votes
2answers
30 views

The Hand Shaking Lemma

In any graph G=(V,E) [the hand shaking lemma] $$ \sum_{v \in V} \deg(v) = 2 |E| $$ (original at http://i.stack.imgur.com/af4en.png) where |E| donetes the number of edges I alredy tried to count ...
0
votes
0answers
37 views

In code sequence of tree replace every 0 with two 0 and every 1 with two 1 will it be tree again?

So i have this question If yes, explain how the structure of this graph depends on the structure of the original subgraph. In not, give an example of such sequence. I just want to be sure if i'm right ...
0
votes
0answers
14 views

Proving the treewidth of a graph is the maximum treewidth of the connected components

We have a graph $G = (V,E)$ and $C$ is the set of connected components of G. I want to prove that $tw(G) \geq $ Max $tw(C)$ where tw is the treewidth. I know the out sketch of the proof is to take ...