5
votes
1answer
18 views

Graph DFS, BFS and some inference

Suppose G is a connected, undirected graph with at least 3 vertexes. we know the order or visiting the vertexes in DFS and ...
-1
votes
1answer
34 views

Can someone tell me how to solve this problem? [on hold]

Let $G$ be a connected graph with $n$ vertices. Let $GT$ be the graph having the spanning trees of $G$ as vertices, with two vertices $s$ and $t$ being adjacent if and only if the corresponding ...
0
votes
1answer
29 views

Graphs that are almost trees

What's the name of rooted trees in which arbitrary connections between vertices of consecutive levels are allowed? (The level of a vertex is its distance to the root.) I.e.: All parents of a vertex ...
4
votes
2answers
70 views
+50

Graph and in-Degree and Drawing

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
0
votes
3answers
31 views

Acyclic graph must have a leaf

It is a theorem that every acyclic graph must have a leaf, ie. A vertex with degree 1 at most. Intuitively, it makes sense as any vertex with more degree would be connected to at least 2 vertices ...
4
votes
1answer
164 views

Graph Min Cut Problem

The idea is to give an Flow Network in which the minimum cut goes through a lot of edges. So adding one unit to each edge will change the min cut. The following figure, as a counter example, shows a ...
0
votes
0answers
24 views

Exactly one minimum spanning tree

A all edges in a graph of n vertices have differing weights. How can I prove that there is exactly one minimum spanning tree?
1
vote
1answer
49 views

$k$-connected graphs containing trees

I've encountered the following problem in the book "Graphs and Digraphs" and I'm not sure how to do it. Show that every $k$-connected graph contains any tree of order $k+1$ as a subgraph.
0
votes
0answers
13 views

Trees and Leaves (Graph Theory)

Let $T$ be a tree with $l$ leaves and $k \in \mathbb{Z}^{+}$ with $2k \geq l$. I need to show that there exists paths $P_{1}, P_{2},...,P_{k}$ such that: (i) $P_{1} \cup P_{2} \cup ... \cup P_{k} = ...
0
votes
2answers
50 views

All self-complementary trees [closed]

I am looking for all self-complementary trees. Could someone accompany me in this great adventure?
0
votes
1answer
30 views

Calculating the average degree/valency of vertices

If I were to let T be a tree with n vertices, what would be the average degree/valency of the vertices in T? How would I go about calculating this?
-1
votes
1answer
73 views

Finding a minimum weight spanning tree? [duplicate]

Letting W be the weighted graph created by taking a complete graph K5 on five vertices 1, 2, 3, 4, 5 with the weight of each edge {x,y} given by ({x,y})=x+y, How would I find a minimum weight ...
0
votes
1answer
60 views

How would I find a minimum weight spanning tree for W?

If I were to let $W$ be the weighted graph formed by taking a complete graph $K_5$ on five vertices 1, 2, 3, 4, 5 with the weight of each edge $\{x,y\}$ given by $(\{x,y\}) = x + y$, how would I find ...
-1
votes
1answer
201 views

Question about trees, Let T be a tree with n vertices

Are my answers correct to these 3 questions? Let T be a tree with n vertices. 1) What is the average degree/valency of the vertices in T? Average Degree of of ...
0
votes
1answer
135 views

How many spanning trees does the cycle graph C2014 have?

How many spanning trees does the cycle graph $C_{2014}$ have? How do I create a bipartite graph and use it to solve this problem?
1
vote
1answer
39 views

Graph theory: tree vertices

How can I calculate the number of vertices of a tree knowing he has 33 vertices of degree 1, 25 vertices of degree 2, 15 vertices of degree 3 and all other vertices of grade 4?
3
votes
1answer
41 views

Proving every tree has at most one perfect matching

In trying to prove that every tree, T, has at most one perfect matching, I came across this idea: ...
0
votes
1answer
35 views

Spanning tree with unique paths.

Let $G$ be a connected graph and let $r∈V(G)$. Prove that $G$ has a spanning tree $T$ such that for every edge of $G$ with ends $u$ and $v$, either $u$ belongs to the unique path in $T$ with ends $v$ ...
0
votes
1answer
25 views

The intersection of $k$ subtrees of a tree $T$ is nonempty.

Let $T_1$, $T_2$, . . . , $T_k$ be subtrees of a tree such that any two of them have a vertex in common. Prove that they all have a vertex in common. Any hints/solutions are greatly appreciated. I am ...
0
votes
1answer
28 views

Find the node that we will reach with a given path on a graph (complete binary tree)

This question is regarding a special case of graph i.e. complete binary tree Consider the following tree :- ...
2
votes
1answer
40 views

Preorder Traversal

For Each Preorder Traversal, we have multiple Inorder Traversal. this is True or False Conclusion? every one would help me and add some detail.
2
votes
1answer
47 views

Visiting Node in BFS and DFS in the same order [closed]

if G be a connected, undirected graph and has at least 3 vertex. we know the order of visiting node from a given vertex in BFS and DFS is the same. which of the following is false? a) G can be a ...
3
votes
1answer
50 views

Shortest path between two vertex

How we can find Shortest path between two vertex in a weighted directed acyclic graph that has positive and negative weight. in O(|V|+|E|)? thanks to all.
1
vote
1answer
25 views

A graph with minimum degree $k+2$ contains any $(k+3)$-vertex tree as a subgraph?

Let $k$ be a positive integer and let $T$ be a tree of order $k+3$. If $G$ is a graph with minimum degree at least $k+2$, prove that $G$ contains a subgraph isomorphic to $T$. Any solutions or hints ...
0
votes
0answers
21 views

Pascal's Identity and Trees

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
0
votes
1answer
35 views

How to understand the perfect binary tree formula?

I got this paragraph by reading "python algorithm", in which it mentioned `some knights participate in an knockout match, how many mathes do they need to produce the winner. It's answer says: I'm ...
3
votes
0answers
39 views

What are the algebraic and topological properties of a tree (graph theory), and what are any possible connections?

I'm a non-mathematician working with trees (mostly rooted and oriented trees). Typically, I understand them as join-semilattices, so they have an implicit algebraic structure: they form a subgroup ...
-1
votes
1answer
112 views

The union of two connected graphs is connected [closed]

Let $G = (V,E)$ be a graph and let $H_1 = (V_1,E_1)$ and $H_2 = (V_2,E_2)$ be two connected subgraphs of $G$ that have at least one node in common. Prove that the graph $H = H_1\cup H_2 = (V_1\cup ...
0
votes
3answers
41 views

How to write a summation function that counts the number of nodes in a tree?

I come from a programming background and am interested in learning how to represent some things as simple equations, as an entry into thinking mathematically. How do you represent a tree structure as ...
0
votes
1answer
49 views

Width and height of binary tree is $\theta(n)$?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
0
votes
0answers
17 views

Tree of arity n: How to call a vertex that has only k (k<n) children?

What is the correct adjective for a vertex in an n-ary tree that has only k children (k < n)? I was thinking of something like "unsaturated", but I don't know if that is the correct word for this. ...
0
votes
1answer
23 views

Proof about spanning tress in graphs

Let $G=(V,E)$ be a graph and $T_i=(V,F_i),i=1,2$ two disjoint spanning trees in $G$. Let $f_1 \in F_1$. Prove that there is $f_2\in F_2 $ such that $T:=T_1-f_1+f_2$ is a spanning tree.
0
votes
2answers
47 views

Prove that if G is a tree in which all vertices have odd degree then G has odd size.

Prove that if G is a tree in which all vertices have odd degree then G has odd size. Good night, do not know how to approach this "prove". Can you give me tips to solve it?. Please.
1
vote
3answers
75 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 ...
0
votes
0answers
41 views

Min. Spanning Tree - Same weight

Prove that every minimum spanning tree of a connected graph, $G$, has the same maximum edge. Intuitively, this makes sense to me. You need to have that heavy edge because that is the cheapest ...
0
votes
2answers
51 views

Tree with $k$ edges is a subgraph of any graph with all vertices of degree $\geq k$.

Let $T$ be a tree with $k$ edges. Let $G$ be a graph where every vertex has a degree of at least $k$. Show that $T$ is a subgraph $G$. I know this implies that in a graph where every vertex is at ...
2
votes
1answer
58 views

How to call a tree with a single branch?

How do you call a tree with only one branch (in other words, where every vertex has maximum one direct successor)?
0
votes
1answer
26 views

Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance
0
votes
2answers
31 views

Number of spanning trees of a graph (behind the formula)

Given $G$ a subgraph of $K_n$ s.t. $G$ has $n$ vertices with adjacency matrix $A$; why is $$\sum_{T \text{ spanning tree of }K_n}\prod_{(i,j)\in T}A_{i,j}$$ the number of spanning trees? I can't get ...
0
votes
1answer
35 views

How to compute a marginal probability

Given a weighted graph, using the Kirchhoff's matrix tree theorem, how can I compute the marginal edge presence probability: $$P_\beta(ij)=Z_\beta^{-1}\sum_{\text{T spanning tree:$(i,j)\in ...
1
vote
0answers
37 views

Find tree diameter or center

I want to find center in a graph that doesn't have cycles. I heard, that this is how I find a diameter: Take random vertex A Find such vertex B, that distance to it is maximal Find such vertex C, ...
0
votes
0answers
20 views

$k$ edge-disjoint $r$-arborescences in an acylic digraph

An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$. I would like to prove the following: I have thought ...
14
votes
2answers
304 views

Does every “balloon” (dragon, tadpole, canoe paddle) admit a graceful labeling?

8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes. ...
2
votes
1answer
56 views

Mathematics of genealogical trees

I really searched a lot but did not find anything meeting my needs: A place where questions of genealogy, especially the structural and combinatorial analysis of genealogical "trees" of descendants ...
3
votes
0answers
42 views

maximizing the inverse degree in a graph

The inverse degree in the graph $G$ is defined as \begin{align*} r(G) = \sum_{i=1}^N \frac{1}{d_i}, \end{align*} where $d_i$ is the degree of node (vertex) $i$. Is the connected graph with maximum ...
1
vote
1answer
23 views

Prove that every subgraph of forest has at least one vertex of degree < 2

So I know that a forest is a graph that has no cycles. This is what I had in mind: Assume that we have the subgraph T, which has two options: to be connected or not. if it's connected it has to be a ...
0
votes
1answer
25 views

Finding the number of spanning trees on a set of vertices.

I need to find the number of spanning trees on $V = \{1,2,3,4,5,6,7,8,9\}$, where $\{1,2,3,4\}$ are leaves. Can anyone tell me how?
1
vote
3answers
82 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 ...
2
votes
1answer
59 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 ...
2
votes
1answer
171 views

Generating function for vertices distance from the root in a planar tree

I need you help to solve this problem: Consider a planar tree with $n$ non-root vertices. Give a generating function for vertices distance $d$ from the root. Proof that the total ...