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

Existence of infinite subsequence of trees with a subtree contained in the sequence

Assume a statement: For every infinite sequence of rooted trees $\{T\}_{i=0}^\infty$ there is an index $j\geq0$ such that there are infinitely many trees in $\{T\}_{i=0}^\infty$ which contains ...
1
vote
3answers
135 views

is MST a Steiner tree?

I am a little bit confused about MST and Steiner tree? Is an MST a steiner tree?? and suppose we are given a weighted undirected connected graph G = (V,E) and S ⊆ V is the smallest subtree of an MST ...
1
vote
1answer
49 views

Graph G with two Spanning Trees

Let's assume that Graph $G = <V,E>$ has two Spanning Trees $G_a = <V, T_1>$ and $G_b = <V,T_2>$ where $T_1 \cap T_2 = \emptyset$ and $T_1 \cup T_2 = E$. Prove that $\chi(G) \le 4$ ...
1
vote
2answers
936 views

single elimination tournament, don't understand question?

A single elimination tournament is performed in rounds. In each round the teams each play exactly one game and the winners continue, and the losers are knocked out of the competition. So, in each ...
1
vote
3answers
2k views

Sufficient conditions on degrees of vertices for existence of a tree

I am answering a question for an assignment, but I am not sure if my proof is valid, can someone look at it for me? the question: "there is a tree with $p$ vertices. If $d_1, d_2, \dots , d_p$ are ...
1
vote
1answer
27 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 ...
1
vote
1answer
13 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
1answer
24 views

Interpreting a nonstandard definition of a tree

Definition: A tree is a triple $(T,\sigma,\pi)$ where $T$ is a set and $\sigma$ is a so-called successor function from $T$ to the set $T^*$ of all nonempty subsets of $T$, together with a surjective ...
1
vote
1answer
27 views

Using Euler's theorem to calculate the number of edges in a graph

I want to use Euler’s theorem for planar graphs to proof that for a tree $T = (V, E)$ that $|V | = |E| + 1$. Now It's very obvious that a tree is a planar graph since it is connected and there is no ...
1
vote
1answer
211 views

The number of pendant vertices in a tree

Let $T$ be a tree with vertices $\{v_1, v_2, . . . , v_n \}$ for $n \geq 2$. Prove that the number of pendant vertices in $T$ is equal to $$\large{2 + \sum_{v_i,deg(v_i) \geq 3}\big( deg(v_i) - 2 ...
1
vote
2answers
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 ...
1
vote
1answer
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. ...
1
vote
1answer
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, ...
1
vote
1answer
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 ...
1
vote
1answer
40 views

Prove that in the union of two trees there exist a vertex with degree of at most $3$

Let $T_1=(V, E_1), T_2=(V,E_2)$ be trees on the same set of vertices, and let $G=(V,E_1 \cup E_2)$ be the graph resulting from the union of the two trees. Prove that there exist a vertex with ...
1
vote
1answer
247 views

Sentences, Formal Grammars with derivation (parse) trees

I've been reading / studying formal grammars for the past few weeks and I came across a question that puzzled me and I cannot seem to get my head around it for some reason. ...
1
vote
1answer
375 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
1answer
33 views

Proof of a tree with a vertex of degree k and less than k vertices of degree 1

The question is : Does there exist a tree with a vertex of degree k and less than k vertices of degree 1? I tried a lot but it is impossible to find. There is no tree with a vertex degree k and less ...
1
vote
3answers
94 views

Proof of an $\iff$ statement on binary trees

Let $x$ and $y$ be two nodes of a binary tree $B$. Prove that $x$ is an ancestor of $y$ $\iff$ $x$ stands before $y$ in the pre-order traversal of $B$ and $x$ stands after $y$ in the ...
1
vote
2answers
59 views

Proof that spanning trees can be converted into one another

Let $T_1$ and $T_2$ be two spanning trees of a graph $G$. Prove that if $e$ is an edge of $T_1$, there exists an edge $f$ in $T_2$ so $T_1-\{e\}+\{f\}$ also is a spanning tree. For $\{e\}\subset ...
1
vote
2answers
153 views

How to go from Tree to Total orders

Given a tree $T=(X,E)$, is it guaranteed for any orientation of the edges $E$, there exist a strict total order preserves it? For instance, let $X=\{x_1,x_2,..x_n\}$ and $E=(x_i,x_{i+1})$ the result ...
1
vote
2answers
324 views

How to prove that the smallest asymmetric tree has at least 7 vertices?

Find the smallest possible number of vertices an asymmetric tree can have (i.e. prove that no smaller tree can be asymmetric). I think that the answer is 7, but I don't know how to prove it.
1
vote
2answers
120 views

In a tree, is there always a sink where every longest path ends in?

Let $T$ be an undirected tree. Can we always find a leaf vertex $s$ such that every longest path of $T$ has its other endpoint in $s$? It's easy to see that every longest path passes through the ...
1
vote
1answer
44 views

Connection Trees and Partition

In our lecture we just had a short excursion into the tree-world. But the professor mentioned some connection between Ramsey and König's Infinity Lemma (If $T$ is a tree of hight $\omega$ with all ...
1
vote
2answers
269 views

Draw Graph from distance to other nodes

I have a matrix that shows the distance from a node to another node: A B C D E A 0 2 4 3 1 B 2 0 2 1 3 C 4 2 0 2 1 D 3 1 2 0 2 E 1 3 1 2 0 To clearify: The 2 ...
1
vote
1answer
583 views

What is the length of the Minimum Spanning Tree

What is the length of the Minimum Spanning Tree for the following weighted graph? Solution. The length of any minimum spanning tree for this graph (and there is more than one) is 60. The graph and ...
1
vote
1answer
123 views

spanning trees of graphs

Assume we have a simple connected graph G, how would start a prove of the following statement? For any edge of G, there is a spanning tree of G that contans it. I have decided that this is a true ...
1
vote
1answer
313 views

For BSP generation, How to intersect or locate a triangle with a plane defined by another triangle?

I've hit a stumbling block in my project to draw the Utah teapot. I want to generate a binary space partition tree of a set of 3D triangles. The decision step in the recursive tree-construction ...
1
vote
2answers
184 views

existence of a spanning tree

Let $T$ and $T'$ be two spanning trees of a connected graph $G$. Suppose that an edge $e$ is in $T$ but not in $T'$. Show that there is an edge $e'$ in $T'$, but not in $T$, such that ...
1
vote
1answer
37 views

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves $\Rightarrow \exists!$ a maximal independent set.

If $G$ is a tree and $\forall v_1, v_2 : dist(v_1, v_2)$ is even, where $v_1, v_2-$ are leaves of the tree $\Rightarrow \exists!$ a maximal independent set. Give some clue please! Thanks anyway!
1
vote
1answer
323 views

Prove equivalence of conditions for a tree

Let $G=(V,E)$ denote a nonempty graph. Show that the following conditions are all equivalent. $G$ is a tree. Any two vertices in $G$ can be connected by a unique simple path. $G$ is ...
1
vote
1answer
175 views

Existence of a spanning tree with certain properties

Let $\Gamma$ be a finite, connected graph (multiple edges between two vertices are allowed). Fix a vertex $u_0\in V\Gamma$. Does there exist a maximal subtree (i.e., a spanning tree) $T\subset\Gamma$ ...
1
vote
1answer
219 views

Depth distribution of normalized decision trees?

Lets work with the following inductive definition of a decision tree: 1) $\bot$, $\top$ are decision trees. 2) If $x_i$ is a variable and $T_0$, $T_1$ are decision trees then $(\lnot x_i \land T_0) ...
1
vote
2answers
595 views

Graph - Minimum spanning tree

I have a graph with a cycle ($v_1,\ldots,v_k, v_1=v_k$). Claim: If there is a cycle with 2 edges of the same weight, and they are the heaviest edges in this cycle, then there is more than one Minimum ...
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 ...
1
vote
1answer
30 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
22 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 ...
1
vote
1answer
58 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
57 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
35 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 ...
1
vote
1answer
43 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 ...
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 ...
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
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" ...
1
vote
1answer
132 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] ...
1
vote
1answer
77 views

Finding connected components of the graph [duplicate]

suppose that I have the following undirected graph with the following adjacency matrix showing if there is an edge between the nodes: \begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 ...
1
vote
3answers
43 views

Finding element in binary min-heap

I am trying to answer two questions. Can some one check my answer and let me know if its correct or not? Question 1: Which locations in a binary min-heap of n elements could possibly contain the ...
1
vote
1answer
31 views

Prove that minimum spanning tree is a tree

From the the Wikipedia page Minimum spanning tree: A minimum spanning tree is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total ...
1
vote
1answer
22 views

Set of edges not contained in any spanning tree

The question is as follows: Prove that in a graph $G$ a set of edges $X$ which is not contained in any spanning tree is a cycle (or possibly an edge disjoint union of cycles). My thoughts: Proceed by ...
1
vote
1answer
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 ...