All Questions
Tagged with planar-graphs connectedness
11
questions
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
2
votes
1
answer
113
views
Planar Graph Cycle Proof (boundary walk question)
Prove that if G is a 2-connected plane graph, then the boundary walk
of every face of G describes a cycle.
What does this question mean by boundary walk? I have tried looking it up but do not quite ...
- 794
1
vote
1
answer
71
views
A question regarding Graph embedding in plane
I am new to Algebraic Topology. So, I would like to have a detailed proof of this following problem as there are many similar and corollary problems in the book that I am reading.
Suppose we are given ...
- 13
2
votes
1
answer
333
views
Eulerian formula proof by induction on edges question
Proof: Let $f, e, v$ denote the number of faces, edges, and vertices, respectively,
in a planar graph. Use induction on $e$ to prove that $f = e−v + 2$ (this
is known as Euler’s formula).
I think few ...
- 307
1
vote
1
answer
473
views
Maximum connected components after removing 2 vertices
Let a 3 regular, 2 connected (but not 3 connected) , bipartite, planar graph. After removing 2 vertices, how many connected components can there exist at most? I have created an instance with 3 (below)...
- 473
3
votes
1
answer
63
views
Which members of a particular family of graphs are either connected or planar?
I have a graph defined for any $n\in\mathbb{N}$, that is, $G_n=(V_n,E_n)$. Vertices are defined as every $n$-tuple over $\{0,1\}$. Two vertices $u=(u_1,u_2,\dotsc,u_n)$ and $v=(v_1,v_2,\dotsc,v_n)$ ...
- 2,091
1
vote
1
answer
1k
views
Maximal planar graph
A maximal planar graph $G$ with at least 3 vertices is a simple finite planar graph for which we cannot add any new edge $e$ such that $G \cup e$ is still planar. Is there an easy and rigorous way to ...
- 1,353
1
vote
0
answers
46
views
possible embeddings for a $2$-connected planar graph
When I asked the question "cycles and faces in planar graphs", I learned that the
numbers of vertices in the faces are not unique, if the planar graph is only $2$-connected.
My question now is : How ...
- 85.1k
3
votes
1
answer
568
views
Planar graphs and connectivity
How many edges must a planar graph with $n$ nodes have that it is sure that it is
a) connected
b) biconnected
c) triconnected
In particular, are all planar graphs with $n$ nodes and $3n-6$ edges ($...
- 85.1k
4
votes
1
answer
2k
views
What is the smallest $5$-vertex-connected ($5$-edge-connected) planar graph?
A planar graph cannot be $6$-connected because the number of edges of a planar
graph with $n$ vertices is at most $3n-6$, while a $6$-connected graph with $n$ vertices
must have at least $3n$ edges.
...
- 85.1k
2
votes
0
answers
2k
views
Let $G$ be a simple graph with at least $11$ vertices. Prove that either $G$ or its complement $\overline{G}$ must be nonplanar. Connectivity?
I have seen many solutions to this problem and understand all of them, but I keep thinking they are over simplified because the connectivity of $\overline{G}$ is not addressed.
Solutions in general ...
- 123