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

Finding the probability using a tree.

Let's say a specific exam has 3 levels (I, II, III). The candidates who pass the first exam are then eligible to take the next level of the exam. Let's say the pass rates for levels I, II, and III are ...
0
votes
1answer
15 views

Treewidth Of Graphs And Chordal Completion

https://en.wikipedia.org/wiki/Treewidth The above page explains what a tree decomposition is, and states that treewidth of G is equal to the minimum clique number, minus one, of a chordal ...
3
votes
2answers
30 views

You can always delete a vertex from a tree $G$ such that the remaining connected components have size at most $|V(G)|/2$.

I want to prove the statement in the title: for any tree on $n$ vertices, it is possible to delete a vertex such that the deletion leaves connected components with at most $n/2$ vertices each. I drew ...
0
votes
0answers
14 views

Finding Height, Number of Leaves, and Value at of Each Node on Recursive Trees

I have an exam tomorrow and am struggling to understand how to get the height of a tree, the number of leaves, and the value of each node. The image is a practice exam. Any tips and help on the first ...
0
votes
0answers
18 views

Domain of Injectivity of Analytic Map

Suppose we have an analytic map $f: \mathbb{D} \to \mathbb{C}$. Then the set of points where the function is not locally injective is a discrete set. Suppose first for simplicity that the points ...
0
votes
2answers
42 views

Proving the number of leaves of a tree. (Graph Theory)

Prove that if a tree has $n$ vertices (Where $n\geq 2$)and no vertices has degree of $2$, then $T$ has at least $\frac{n+2}{2}$ leaves. Prove by contradiction Suppose that $T$ has less than $\frac{n+...
1
vote
1answer
37 views

Minimum spanning tree of graph? proof by contradiction?

this is not a homework but I need to understand it before my exam tomorrow. How to prove by contradiction that a minimum spanning tree of a graph G is unique if all the edge weights in G are distinct?...
0
votes
0answers
39 views

Diameter of subtrees

Can some one explain how this guy is calculating the centers of all subtrees in $O(n)$. I couldn't understand it. Here is the Quora link A part of his answer claims the following: 4) Find centre of ...
3
votes
1answer
51 views

Infinite graph theory: What's a tree?

Consider a finite graph $G$: $G$ is a tree if it satisfies any of the following equivalent conditions: (1) $G$ is connected and no cycle can be a subgraph of $G$. (2) $G$ is connected and no cycle ...
0
votes
0answers
13 views

number of nodes in Balance binary tree, Full binary tree Complete binary tree

How can I calculate the number the number of nodes in Balance binary tree, Full binary tree Complete binary tree? For the perfect binary Tree, I found the formula $2^{h+1}-1$.
0
votes
1answer
33 views

Verify directly that are exactly 125 labelled trees on 5 vertices.

I know Cayley's formula. However, I need to count them without using the formula. Such a tree has $5-1=4$ edges. Let the degrees of vertices be $d_1,d_2,d_3,d_4,d_5$. By handshaking lemma $d_1+d_2+d_3+...
-1
votes
1answer
21 views

Maximum number of strict binary trees that can be made, each having exactly n leaf nodes.

I am trying to evaluate(Mathematical expression) the number of strict binary trees that can be made with n leaf nodes. I already know that a strict binary tree with n leaf nodes would have exactly ...
0
votes
0answers
20 views

Uniqueness of spanning trees made using search algorithms?

For undirected graphs, the corresponding spanning trees can be obtained using various search algorithms like Depth-first search algorithm , Bredth-first algorithm, etc. I am not sure whether the ...
0
votes
1answer
33 views

How to define a set of trees recursively?

In particular, consider the set of integer-labelled binary trees (T). How could this set be defined in a recursive way from $\mathbb Z$ and T itself? Examples: $(-2, 1, (3, 1, 0)) \in T$ $(-1, (7, 2, ...
2
votes
1answer
58 views

How do I know when to use a Venn diagram or a probability tree? Also, when can I assume that the events are independent?

I have 2 specific problems, one 'requiring' me to use a probability tree, and the other a Venn diagram. I know that apparently the Venn diagrams can be converted into probability trees and vice versa, ...
1
vote
1answer
32 views

What function describes this problem of every possible breeding of a set of dogs?

If I have n dogs [a, b, c, ...], and I want to breed them in every possible combination (every possible binary tree made of ...
1
vote
1answer
25 views

Bounding the probability of landing at any point for a random walk on a tree

Fix $m\geq 2$ and a vertex $v_0$ in an infinite connected $2m$-regular tree, (in other words, the Cayley graph for the free group on $m$ generators) and consider the random walk on the tree starting ...
0
votes
0answers
23 views

Are these tree-related concepts redundant?

I've been doing a lot of work with trees lately, and have developed vocabulary that I've been using to describe them. Not having that strong of a background in graph theory, it occurred to me that I ...
1
vote
1answer
23 views

Cuts on complete binary trees

Claim : Suppose we have a complete binary tree of height $h$. We introduce a cut to partition this tree into two sets of vertices of size $x$ and $2^h - 1 - x$ for some $x$. For any $x$, we define the ...
2
votes
0answers
41 views

How Many Ways to Construct Trees With No More Than 4 Connections per Vertex.

I am a high school student (so sorry if my thinking is way off) with a problem related to chemistry essentially dealing with the number of ways you can arrange carbon atoms in a alkane. I saw that ...
3
votes
1answer
45 views

Bona “A Walk Through Combinatorics” Problem 10.29

Given a tree $T$, define the "total distance" of a vertex $v$ by $$ td(v) = \sum_{w \in V(T)} d(v,w), $$ where $d(v,w)$ is the number of edges in the unique $vw$-path in $T$. In any tree, the value of ...
0
votes
0answers
19 views

Parsing a definition concerning trees and tuples

Definition: Let $T$ be a tree. Given a set $X$, we define a $T-tuple$ of elements of $X$ to be a function x: $T\rightarrow X$ Alternatively, we sometimes refer to a $T$-tuple as a tree of elements ...
2
votes
1answer
40 views

Constructing every spanning tree from addition and deletion of edges

Let $G = (V,E)$ be given (note that this is not necessarily simple), and consider the set of every spanning tree of $G$, $S$. Choose any $G_a, G_b \in S$. Is it possible to construct $G_b$ from $G_a$ ...
0
votes
2answers
63 views

Relation between vertices and edges in a tree?

I know the following relation between vertices and edges of a tree - Any connected graph(undirected) with n vertices and $n-1$ edges is a tree. My question is suppose I have an undirected connected ...
0
votes
1answer
39 views

Finding log base 2 of a number .

I generally visualize $\log_{2}$ of a number as an inverted binary tree, for example to know how many times 8 needs to be divided to become one I image a inverted tree of 8 leaves then, the level ...
0
votes
2answers
36 views

How many vertices are of degree 1?

Given $T(n,m)$ which contains only vertices of degree 1 and 3. How many vertices are of degree 1? Is it similar to compute in thi link? How many vertices of degree 1 in a tree? Thank you.
1
vote
1answer
63 views

Closed Form for Sum of Nodes in Binary Tree

Consider a binary tree $T$ with nodes in $\mathbb{Z}^+$, where level $k$ of $T$ contains nodes $2^k$ through $2^{k + 1} - 1$. I have some problems that involve visiting the nodes of $T$ in their ...
1
vote
1answer
15 views

Number of Plane Oriented Recursive Trees

The number of plane oriented recursive trees is $(2n-3)!!$ I understand that given a vertex $v$ with $k$ successors, there are $k+1$ ways to attach a new vertex to create a new tree of size one ...
1
vote
0answers
27 views

Entropy of a dictionary

I have an english dictionary (a file that contains a list of words) and I want to calculate: given a path tree (a word), measure $H(C_{l+1}|C_l=c_l, C_{l-1}=c_{l-1}, ...)$ for a few levels of the ...
3
votes
1answer
73 views

Set Theory: Tree Property

Why does the tree property hold for regular cardinals but not singular cardinals? (I.e. There exists a tree of height $\kappa$ with countable levels and no cofinal branch for $\kappa$ a singular ...
1
vote
0answers
16 views

Example of a Shortest Path Tree for a Directed Graph that contains a directed cycle of negative length

My colleague says this is possible, but I don't understand how. I know it is necessary for the directed Graph to contain no negative cycles in order to prove that the Shortest Path Tree exists. So I ...
0
votes
2answers
41 views

Black Depth in Red-black Tree?

Wikipedia's Red-black tree states the last property of a Red-black tree: Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes. Some definitions: ...
1
vote
1answer
60 views

Depth-first search binary tree problem

Professor Hastings has constructed a 23-node binary tree in which each node is labeled with a unique letter of the alphabet. Preorder and postorder traversals of the tree visit the nodes in the ...
1
vote
1answer
36 views

Relationship between ordered trees and integer partitions

I've found that there is a bijection between integer partitions and ordered rooted trees with roots of degree 2 or greater. The rigorous proof is complicated, but the gist of it is that you take the ...
3
votes
1answer
43 views

Must a minimum weight spanning tree for a graph contain the least weight edge of every vertex of the graph?

Currently learning about spanning trees and using Kruskal's algorithm and I was wondering whether a minimum weight spanning tree of a weighted graph must contain one of the least weight edges of every ...
0
votes
2answers
31 views

Proving that the number of full nodes + 1 is equal to the number of leaves in a nonempty binary tree

I am looking at the proof of this and I am so completely lost on where they are getting some of the expressions. Here is the proof: Consider that $N$ is the number of nodes, $F$ is the number of full ...
0
votes
1answer
60 views

Finding a minimum spanning tree in a graph with edge weights in {1,2,.., R} where R is constant

I have recently been doing some research into algorithms for finding minimum spanning trees in graphs, and I am interested in the following problem: Let G be an undirected graph on n vertices with m ...
1
vote
1answer
30 views

Set Theory: Graphs and $k$-Colorings

Let $G = (V, E)$ be a graph with $V = \omega$. Show that if for all $n < \omega$, the graph $G_{n} = (n, E \cap [n]^{2})$ is $k$-colorable, then $G$ is $k$-colorable. I know how to prove this ...
1
vote
1answer
31 views

Is there a way to obtain exactly 2 quarts in the 8-quart or 5-quart pitcher?

Suppose we are given pitchers of waters, of sizes $12$ quarts, $8$ quarts, and $5$ quarts. Initially the $12$ quart pitcher is full and the other two empty. We can pour water from one pitcher to ...
0
votes
2answers
30 views

Show that a simple connected graph G contains a cycle if and only if it contains more than one spanning tree.

This doesn't seem like a huge leap to prove this statement. However, I'm having trouble writing out a proof formally. I understand that I need to prove two directions. Thanks for your help
2
votes
2answers
114 views

Determine depth of node in perfect binary tree with depth-first in-order enumeration

Given a perfect, balanced and complete binary tree of height H with its nodes enumerated depth-first in-order, what formula can you use to calculate the depth of a node given its index in constant ...
0
votes
0answers
10 views

Clustering via U(-W)PGMA

Given paiwise distance between 5 taxa: {a,b,c,d,e} 0 3 12 12 9 - 0 13 13 10 - - 0 6 7 - - - 0 7 - - - - 0 Calculate evolutionary tree, using UPGMA and ...
2
votes
1answer
114 views

Proving the smallest number of leaves in a tree

What is the smallest number of leaves in a tree with two vertices of degree 3, one vertex of degree 5 and two vertices of degree 6? I've come up with what I think is the correct drawing containing ...
1
vote
1answer
45 views

Can there be a walk between a tree and it's subgraph formed by removing an edge from the tree?

Say T is a tree and e is an edge in T. H is a subgraph of T obtained by removing edge e in T. Can there be a walk in H that connects to T? Edit: I've been trying to work it out, and what I have is ...
0
votes
0answers
27 views

Graph containing every tree

Let $G$ be a graph on $n$ vertices of size at least $(k-1)n - {k\choose 2} +1$. Show that $G$ contains all trees of order $k+1$. What I really would like to show is that there is a subgraph of ...
1
vote
1answer
23 views

How many types of distinct Binary Tree can be formed with a height of h?

How many types of distinct Binary Tree can be formed with a height of h? if we only know the height of binary tree, and we regard root-left and root-right as the same tree structure, this means if the ...
2
votes
1answer
48 views

Adding one edge to a tree creates exactly one cycle

I am having trouble proving this question. I am also having trouble visualizing how this works, using a binary tree as an example. I don't see how adding an edge creates one cycle? Isn't a cycle ...
1
vote
0answers
44 views

Determine Huffman Tree Depth Using any combinactory ways?

I see this link for determining depth (height) of Huffman tree, but not useful for me. My Question is: Knowing the frequencies of each symbol, is it possible to determine the maximum height or ...
1
vote
1answer
16 views

Number of full orderings in a full binary tree.

I'm trying to resolve an example from book. T = (V, E) is a full binary tree, and |V| = n. Show that there exist ...
1
vote
2answers
76 views

Number of binary search tree of height $6$

The number of ways in which the numbers $1, 2, 3, 4, 5, 6, 7$ can be inserted in an empty binary search tree, such that the resulting tree has height $6$, is______ . Note: The height of a tree with a ...