All Questions
Tagged with planar-graphs discrete-mathematics
156
questions
1
vote
0
answers
33
views
Degree of the neigbour verticies of a vertex degree 5 in a planar graph - visualization
I'm writing a lecture on 5-coloring planar graphs and I'm having trouble visualizing this inequality form the proof
"$2n_5 \leq \sum_{d \geq 12} dn_d$"
I want to make a simple drawing of ...
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
2
votes
1
answer
60
views
Number of edges in planar bipartite graph.
Suppose G=(V,E) is a planar bipartite graph such that $V_1$ and $V_2$ are the partite sets. Suppose for all $a \in V_1$, $deg(a)\le p$ and for all $b \in V_2$, $deg(b)\le q$. If $|V_1|=x$ and $|V_2|=y$...
3
votes
2
answers
319
views
Prove or Disprove: Is there a connected planar graph with an odd number of faces where every vertex has a degree of 6?
Prove or Disprove: Is there a connected planar graph with an odd number of faces where every vertex has a degree of 6?
I know,
Theorem: In a connected planar graph where each vertex has the same ...
- 69
2
votes
1
answer
339
views
Can a connected planar graph have 10 vertices and edges? is this possible?
Can a connected planar graph have 10 vertices and edges? is this possible?
Using Euler’s formula, $V − E + F = 2$.
$10 − 10 + F = 2$,
Therefore $F = 2$.
Do I also need to use this formula: $2E$ $\geq$ ...
- 69
3
votes
1
answer
39
views
Simple graph $G$ can be represented as union of $2$ edge-disjoint graphs
I'm trying to prove the following statement:
Prove that any simple graph $G$ can be represented as the union of $2$ edge-disjointed graphs $G_{1}$ and $G_{2}$, where $G_{1}$ is acyclic and $G_{2}$ ...
- 367
0
votes
0
answers
39
views
Sequence of degrees of a graph with two colors
With respect to the graph
Another concept central to an understanding of fractional isomorphism is that of the iterated degree
sequence of a graph. Recall that the degree of a vertex $v\in G$ is the ...
- 509
0
votes
0
answers
65
views
The final step of proving Kuratowski’s Theorem
Recently when I read the proof of the Kuratowski’s Theorem, I was stuck at the final step where it States 4 cases (Since this proof uses many lemmas, it is difficult to give one context related with ...
- 416
0
votes
1
answer
108
views
Planar graphs and isomorphism
If I have a planar graph G and another graph H that's been created by crossing two edges of graph – and its very obviously non-planar. Can I use it as an argument to show that they can not be ...
- 397
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
2
answers
155
views
Heptagon is divided into pentagons and hexagons. Prove that there are at least $27$ pentagons in this division.
A heptagon is divided into convex pentagons and convex hexagons in such a way that each vertex of the heptagon is the vertex of at least three polygons of the division.
Prove that there are at least $...
- 1,086
2
votes
0
answers
86
views
Proof of $e\leq3v-6$ for planar graphs without Euler's formula
For a short talk for an audience not familiar with graph theory I want to give an informal proof that $e\leq3v-6$ holds in all planar graphs with $v>2$ and I don't want to use Euler's formula. My ...
- 6,649
1
vote
0
answers
41
views
How best to model "stream puzzle" games?
A number of puzzle games around the 00s had mechanics based around manipulating streams of objects towards sinks on a grid map, with the level being passed when a certain number of objects had been ...
- 640
0
votes
1
answer
39
views
In a planar embedding of a graph, can vertices lie on each other? [closed]
I am wondering if vertices of a planar graph can lie on top of each other in an embedding of the graph. Also, when drawing a picture/representation of the graph, is drawing vertices on top of vertices ...
- 31
1
vote
1
answer
79
views
Why is a non-planar graph still non-planar after subdividing it?
A graph $H$ is said to be a subdivision of a graph
$G$ if $H$ can be obtained from G by successively deleting an edge in $G$, and replacing that edge with a length
2 path (whose central vertex was not ...
- 3,019