# Questions tagged [trees]

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.

1,670 questions
Filter by
Sorted by
Tagged with
27 views

13 views

### Constructing a crown graph given an independent set [closed]

A crown in a graph G is a pair (H, C), where H ⊆ V(G) and C ⊆ V(G) with $H ∩C = ∅$ such that the following conditions hold: (a) The set of neighbors of vertices in C is precisely H, i.e. $H = N(C)$, (...
32 views

### Unsure of graph isomorphism

Are the following sets of graphs isomorphic? I believe the first set (the rooted trees) are, and with the second set (the free trees), I notice that both trees have 2 vertices with degree 3, one with ...
37 views

### Proving Cayley s formula from a sum

I need to prove $\sum\limits_{i=0}^n\binom{n}{i}i^{n-2}(-1)^{n-i+1}=0$ The above can be written as $\left(\sum\limits_{i=0}^{n-1}\binom{n}{i}i^{n-2}(-1)^{n-i+1}\right)-n^{n-2}=0$ So I need to prove ...
32 views

### The trees $T_i$ and $T_j$ have a vertex in common. Show that $T$ has a vertex which is in all of the $T_i$.

Let $T_1, \ldots, T_k$ be subtrees of a tree $T$ such that for all $1 \leq i < j \leq k$, the trees $T_i$ and $T_j$ have a vertex in common. Show that $T$ has a vertex which is in all of the $T_i$. ...
60 views

### Does any connected graph G have a spanning tree T with the same domination number?

Let $G$ be a simple graph. A spanning tree of a connected graph $G$ is an acyclic connected subgraph $T$ of $G$ such that $V_T = V_G$. A dominating set of $G$ is a subset $W$ of $V_G$ such that every ...
23 views

### How many spanning trees are there in the $n$-cube $Q_n$?

For an integer $n \geq 1,$ how many spanning trees does the $n$-cube $Q_n$ have? Put another way, what is the formula for the number of spanning trees of the $n$-cube $Q_n?$ Can you help me? Thank you ...
47 views

### Number of leaves in tree

If G is tree with 18 vertices, with max degree of vertex 6 and with no vertices of degree 2, prove that number of leaves $l$ satisfies $12\le l\le 14$. From handshaking lemma I get that $l\ge 10$, ...
54 views

### König's Lemma in set theory, why is the finite branching needed?

The answers here are quite mathematical. I hope somebody can explain this particular point here. Why is it for a tree with height $\omega$ that all its levels need to be finite in order to have an ...
53 views

A quadrivalent tree is a tree where each vertex has degree 1 or 4. I was recently given this problem, and have searched online and could not find anything to help me start this: If a quadrivalent tree ...
22 views

### Laver forcing, trees and stems

In the following snippet about Laver forcing I do not understand several things: what is the intuition behind that $T$ extends $S$ if $T\subseteq S$. Second, is by a stem meant ambiguously any node of ...
30 views

### Is my Graph Theory proof accurate ? Tree proof

Poof: A tree with n vertices has n-1 edges Let us assume a tree $T = (V,E)$ such that $|V| = n,$ we know that trees are minimally connected (1-connected) graphs, and that they are maximal acyclic ...
35 views

### Let $G$ be a tree and $V_0 = \left \lbrace v \in V(G) | deg (v) = 1 \right \rbrace$. Show that $G \setminus V_0$ is a tree.

Let $G$ be a tree and $V_0 = \left \lbrace v \in V(G) | deg (v) = 1 \right \rbrace$. Show that $G \setminus V_0$ is a tree. To see that this is true, to demonstrate: $G \setminus V_0$ is ...
527 views

### Can we “complete” the standard binary tree to have a “level at infinity”?

Consider the standard binary tree. Clearly the number of nodes is a countable infinity. Each node can be mapped bijectively to a rational number. But if we go ahead and "union the tree" with ...
40 views

### Showing that any tree has a separator vertex such that the size of the separated components is at most $\lfloor\frac{k}{n}V(G)\rfloor$

The task is to show that one can always find such a separator vertex in a tree $T$ such that the created components have a size of at most $\lfloor\frac{k}{n}V(G)\rfloor, \frac{k}{n} \in (0, 1)$ in ...
124 views

### Number of Isomorphic Trees

Given $p = cn^{−1−1/m}(1 + o(1)), m ∈ N, c > 0.$ Prove that the number of components in $G(n, p)$ isomorphic to a tree on $m + 1$ vertices converges to a $Pois$($\frac{c^m(m+1)^{m−1}} {(m+1)!}$)...
21 views

### stretching trees (graph theory) ($n$-cube graph) [closed]

What is the number of including trees of $n$ $cube$ graph?
17 views

### Total number of spanning trees of K7 if one edge is deleted [duplicate]

For a complete graph, the total number of spanning trees can be calculated as $n^{(n-2)}$. But my question is what will be the total spanning trees if one edge is deleted from it? My approach: Total ...
16 views

### How to count the number of subtrees in a m-ary tree that is subgraph isomorphic to a another m-ary tree?

Let there be two directed $M$-ary ($k$-ary) trees, $T_a$ and query tree $T_b$. I'm interested to find how many subtrees $|S_a|$ there are in $T_a$ that is subgraph isomorphic to $T_b$. $T_a=$ data ...
54 views

43 views

### Examples of non-free group actions on trees with finite edge-stabilizers

I am interested in finding examples of finitely-generated non-free groups $H$ such that $H$ is a finite index subgroup of some group $G$ and $H$ acts without edge-inversion on some tree $T$ with ...
55 views

### Let $G$ be a connected graph $a \in E (G)$, they are equivalent

Let $G$ be a connected graph $a \in E (G)$, they are equivalent: a) $a$ is a bridge of $G$. b) $a$ does not belong to a cycle c) There are $u, \: v \in V (G)$ such that every $uv-$path ...
28 views

### Let $G$ be a tree with $n$ vertices. Show that the following statements are equivalent:

Let $G$ be a tree with $n$ vertices. Show that the following statements are equivalent: a) $G$ is the path with $n$ vertices. b) $G$ has a maximum degree of two. c) $G$ has exactly two ...
55 views

### Practice exercise | Trees | Graph theory

Let $G$ be a tree with 14 vertices of degree 1, and the degree of each nonterminal vertex is 4 or 5. Find the number of vertices of degree 4 and degree 5. My attempt, summarized, is the following: ...
42 views

### Let $G$ be a graph other than the trivial one, with exactly one vertex of degree 1. Show that $G$ cannot be a tree.

Let $G$ be a graph other than the trivial one, with exactly one vertex of degree 1. Show that $G$ cannot be a tree. Proof. Since we know that every tree has $n-1$ edges, then the total degree of ...
37 views

### Let $G$ be a connected graph $a \in A (G)$, they are equivalent:

Let $G$ be a connected graph $a \in A (G)$, they are equivalent: a) $a$ is a bridge of $G$. b) $a$ does not belong to a cycle. c) There are $u, v \in V (G)$ such that every $uv-$ path ...
27 views

### Describe how are the trees with $n$ vertices that have the smallest and the largest possible number of vertices of degree 1.

Describe how are the trees with $n$ vertices that have the smallest and the largest possible number of vertices of degree 1. Affirmation: The trees that have the least number of vertices of degree 1 ...
I am working on Algebraic Combinatorics by Richard P. Stanley. Problem 4 on Chapter 9 reads: Let $p \ge 5$, and let $G_p$ be the graph on the vertex set $\mathbb{Z}_p$ with edges $\{i, i+1 \}$ and $\{... 1answer 31 views ### Exponential Generating Function for certain trees I am trying to find the exponential generating function for rooted labeled plane trees with each vertex in the tree having an even number of children. I am hoping to do this with Lagrange inversion ... 0answers 26 views ### Roots producing isomorphic trees Is there existing terminology for the following property of a rooted tree? I'd like to know how many choices of root node can produce an isomorphic tree. This is different from the number of ... 0answers 10 views ### Semantic tree and quantier rules first let me apologize my english! I am taking a class in logic where we are working on semantic and predicate logic. We were given this to solve as a semantic tree. And honestly I am way too puzzled ... 0answers 32 views ### Understanding the proof of an equivalent condition for a graph to be a tree I am studying graph theory from the book of Harary. There is a proof given in the book for the following: If G is a connected graph and$p=q+1$then G is acyclic, where,$p$= No. of points in the ... 0answers 24 views ### Binary Search Tree Induction [duplicate] So I know that it is true for$n = 1$because$h \ge \log(1)\implies h \ge 0$. I also assume that$n=k$is true. But how would I prove$h \ge \log_2{k+1}$. I tried to through log laws, but I'm quite ... 1answer 24 views ### Example of a Dedekind completion of a tree I'm reading this paper on topologies on trees, and I am unsure of a construction being mentioned in it. Let$T$be a tree. Let$C \subset T$be a chain that is bounded above. Then a pseudo-supremum of ... 1answer 75 views ### Order-theoretic tree with infinitely repeating colouring This seems likely to be an instance of general combinatorial theorem. But which one? Definition 1: Define an order-theoretic tree$T$to be a poset such that for any node, the set of elements less ... 0answers 27 views ### Maximum and minimum possible height of a Binary tree Sorry Sir, I don't know graph theory just helping my friend by asking here. Can you help me by providing the answer and the method you are using? Let T be a binary tree of order 17. Then find the ... 1answer 43 views ### Number of ways to apply a function taking any number of inputs and producing one output to$n$items I have a function, fn that can take any number of inputs and produces one output. The order of the inputs doesn't matter. However, if just one input is passed, the function just returns it as is, ... 1answer 114 views ### Find a weighted graph with$5$vertices has exactly two minimal spanning trees Draw a weighted graph with$5$vertices has exactly two minimal spanning trees and justify that there are no other minimum spanning tree. I could create a random graph which contain one minimal ... 1answer 26 views ### Why do$\prod_{i=1}^{n} c_{i} !$out of the$n!$different ways to label a tree give rise to the same unordered labelled tree? My question is about a sentence in the proof of the following proposition: Proposition 2.3. The uniform random tree$\mathbb{T}_{n}$has the same distribution as a tree generated as follows: Take a ... 2answers 42 views ### Finding the number of spanning tree of a particular graph I have the following graph: start with a graph$C_n$(a n-cycle), where$n$is at least 4, and we label the vertices from$1$to$n$. Now, let an extra vertex$x$be connected to the vertex with label ... 1answer 28 views ### Full Binary Trees - Maximizing the arithmetic mean of powers of leaf node levels. I have a full binary tree with$n$leaf nodes. Therefore we get the following constraint$\sum_{i=1}^{n}2^{-l_{i}} = 1$where$l_i$is the level occupied by each leaf node. I have the metric$\frac{1}...
Given a function $f\colon \Bbb Z\to\Bbb Z$. Assume that for some index set $I$, there are $a_i,b_i,c_i,d_i\in\Bbb Z$ such that $\Bbb Z=\bigcup_{i\in I}(a_i+b_i\Bbb N_0)$ and \$\Bbb Z=\bigcup_{i\in I}(...