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.

Filter by
Sorted by
Tagged with
3
votes
0answers
27 views

Probability that a tripartite directed graph is a tree

Define a directed graph $D$ as follows. The vertices of $D$ are $R \cup G \cup B \cup \{v\}$, where $|R| = r, |G| = g, |B| = b$. We also need some conditions on $r,g,b$: $$r \leq g+b+1, \qquad g\leq r+...
-2
votes
0answers
24 views

Define predicates for graph distance between two vertices [closed]

Define first-order formulas $\phi_1(x,y),\phi_2(x,y),\phi_3(x,y),\dots$ where $\phi_n(x,y)$ holds when "there is a path from $x$ to $y$ of length at most $n$", where $n>0$. You may use a ...
1
vote
1answer
37 views

Is there a way to know how many non-isomorphic spanning trees there are for a graph?

I have a big doubt: Is there a way to know how many non-isomorphic spanning trees there are for a graph? In a Spanning Tree there are no cycles, one less thing to worry about.
7
votes
2answers
71 views

$T_{n}$ a set of all binary trees with $n$ leaves

Let $T_{n}$ be a set of all binary trees with $n$ leaves. Show that: $$|T_1|=1,|T_2|=1,|T_3|=2,|T_4|=5$$ My attempt: I was trying to find how many options of leaves we should add to the previous tree ...
1
vote
1answer
31 views

When does a RAAG act on a Tree?

Show that a RAAG acts on a tree of valence 4, acting transitively on vertices, if at least one pair of vertices is not joined by an edge. I'm trying first to prove that every such RAAG $G$ acts on a ...
0
votes
0answers
20 views

Proof in Graph Theory: if every vertex adjacent to leaf has degree of at least 3 then there exists two leaves who are adjacent to same vertex

I am trying to do some proofs on my own in Graph theory. I just want someone to check if this proof is mathematically sufficient and correct in the first place. I have been struggling to determine ...
-1
votes
0answers
16 views

Tree Traversal Algorithm Use Cases [closed]

When it comes to basic tree traversal algorithms, what would some real life use cases be for preorder, inorder and postorder?
0
votes
0answers
22 views

Matrix theorem for counting number of spanning trees

I have to find number of spanning trees in graph $K_{3,n}$. I am supposed to do this using matrix theorem of spanning trees. So, i need to calculate determinant of this matrix:$$ \begin{pmatrix} ...
0
votes
0answers
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)$, (...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
2
votes
2answers
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$. ...
5
votes
2answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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$, ...
1
vote
3answers
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 ...
0
votes
1answer
53 views

Quadrivalent Trees

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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
7
votes
2answers
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 ...
1
vote
2answers
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 ...
2
votes
0answers
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)!}$)...
0
votes
0answers
21 views

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

What is the number of including trees of $n$ $cube$ graph?
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
54 views

MST theorem intuition

We learned this theorem. Given an undirected graph $G$ with weight function $w : E \rightarrow \mathbb{R}$, if $T$ and $T'$ are two MST's (minimum spanning trees) of $G$, with distinct edges ($𝑇 \cap ...
1
vote
1answer
46 views

Expressing that a tree has an even number of nodes in monadic second order logic

Let $C^{fin}_2$ be the set of finite trees with outdegree at most two considered as a structure in a signature $Child(,)$. I'm trying to find a sentence in monadic second order logic that holds on $T \...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
2
votes
3answers
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: ...
2
votes
1answer
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 ...
0
votes
2answers
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 ...
0
votes
1answer
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 ...
3
votes
1answer
39 views

Prove that the Following Graph Has $p F^2_p$ Spanning Trees

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 $\{...
3
votes
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
2
votes
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 ...
2
votes
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 ...
0
votes
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 ...
2
votes
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, ...
0
votes
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 ...
0
votes
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 ...
2
votes
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 ...
0
votes
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}...
1
vote
0answers
23 views

References for trees and digraphs formed from iterated functions

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}(...

1
2 3 4 5
34