All Questions
Tagged with planar-graphs trees
24
questions
4
votes
1
answer
62
views
Every binary tree with $n$ leaves has a subtree with $k$ leaves where $\frac{n}{3} \leq k \leq \frac{2n}{3}$.
I want to show the following:
Every binary tree with $n$ leaves has a subtree with $k$ leaves where $\frac{n}{3} \leq k \leq \frac{2n}{3}$.
My approach:
First thing I did was to draw a binary tree and ...
- 609
1
vote
0
answers
132
views
How many trees with $n$ vertices correspond to the vector $(g_1,g_2,g_3,g_4)$, where the $g_i$ are the number of vertices of degree $i$?
Let there be a tree with $n$ vertices. How to count the number of trees corresponding to the set $(g_1,g_2,g_3,g_4)$, where $g_i$ is the number of vertices of degree $i$? For example, with $n=8$ we ...
user1253213
2
votes
1
answer
47
views
Suppose a tree graph T with $n\ge 4$ ,and 3 edges $e_1,e_2,e_3$ from its complement tree graph T-.Show that $G = T + e_1 + e_2 +e_3$ is a planar graph
can't seem to find the proof for this problem.
I know that a Tree graph has the property: $n = m - 1$ where $n$ is the number vertices and $m$ is the number of edges.
Also not sure if the restriction ...
- 35
0
votes
1
answer
67
views
How many subgraphs with exactly 6 edges can I make from a complete graph with 7 vertices?
Let the complete graph be unweighted and undirected. The subgraphs can be unconnected.
Edit (More detail): I'm trying to go about this by splitting it up into spanning trees and non-spanning trees ...
4
votes
1
answer
99
views
Suppose $G$ is a bipartite planar graph such that for any two vertices $A$ and $B$
Suppose $G$ is a bipartite planar graph such that for any two vertices $A$ and $B$, the
number of shortest paths from $A$ to $B$ is odd. Prove that $G$ is a tree.
Suppose $G$ is a bipartite planar ...
- 341
2
votes
1
answer
86
views
Do minimum spanning trees drawn on points in $\mathbb{R}^2$ always have non-intersecting edges?
Preamble
This question is motivated by the question "Embedded minimum spanning trees for visualizing effects of dimensionality reduction?".
Suppose I were to begin with a collection of ...
- 1,876
1
vote
1
answer
54
views
Does every 3-valent planar graph admit a maximal tree, which is non-branching?
Consider a $3$-valent (multi)graph without loops, i.e. multiple edges are allowed, but there are no edges starting/ending at the same vertex. Furthermore, lets assume $\gamma$ is planar, which means ...
- 2,876
0
votes
1
answer
108
views
What is a convex combination of graphs?
For example in this paper, they refer to a "convex combination of trees" (pg. 2, first paragraph), and also, more generally, to "convex combination of graphs" (pg. 2, footnote).
-&...
4
votes
1
answer
203
views
Is $T_1+T_2$ planar if $T_1,T_2$ are trees with the same vertices?
I have two trees $T_1=(V,E_1)$ and $T_2=(V,E_2)$.
My question is, supposing that $G=(V,E_1\cup E_2)$, can we conclude that $G$ is planar?
I think it's planar, because $G$ is created by the union of ...
- 341
11
votes
0
answers
301
views
Can every tree with total length $2$ be covered by a semi-disc of radius $1$?
Can every tree with total length $2$ be covered by a semi-disc of radius $1$?
If the tree is actually a curve, or the convex hull of the tree is a triangle, I know this is correct after some attempts. ...
- 954
1
vote
2
answers
395
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 ...
- 1,030
11
votes
0
answers
488
views
Parity on the number of rooted trees
Suppose we have a planar graph with vertices $v_0, \ldots, v_n$, where $n$ is even such that there exist a checkerboard coloring of the regions in the complement such that the black regions are $n$ (...
user895424
1
vote
1
answer
2k
views
show that all trees are planar without using Euler's formula or the fact that all trees are planar
the question is this: Show that all trees are planar
I thought about using Euler's formula to show this but then I was told that I wasn't allowed to assume that trees are connected planar graphs so my ...
user812532
2
votes
1
answer
407
views
Given a binary tree with N labelled leaves, is it possible to find its unique number in the Catalan range?
The question is about finding the inverse to the problem of generating the $n^{th}$ binary tree with N labelled leaves (Generating the $n^{th}$ full binary tree over $N$ labelled leaves).
Let's say if ...
- 21
1
vote
1
answer
2k
views
Find a formula, in terms of n and k , for the number of leaves of G.
Let G be a tree having n n vertices. Suppose that every vertex in G which is not a leaf has degree k, where k > 1 . Find a formula, in terms of n and k , for the number of leaves of G.
I started ...
- 151