All Questions
Tagged with planar-graphs proof-explanation
19
questions
14
votes
10
answers
3k
views
Can you explain to me why this proof by induction is not flawed? (Domain is graph theory, but that is secondary)
Background
I am following this MIT OCW course on mathematics for computer science.
In one of the recitations they come to the below result:
Official solution
Task:
A planar graph is a graph that can ...
- 294
0
votes
0
answers
42
views
Why can we assume a triangulated graph without loss of generality, for proofs of the 4 colour theorem?
In the Wikipedia article about the four colour theorem it is stated
First, if planar regions separated by the graph are not triangulated, i.e. do not have exactly three edges in their boundaries, we ...
- 1,125
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
95
views
Lower bounds on the matching number of maximal planar graphs.
I have read the following article in which the authors briefly prove that the lower bound on the matching number of a maximal planar graph is $\frac{n+8}{3}$.
Biedl, T., & Wittnebel, J. (2023). ...
- 2,474
1
vote
0
answers
25
views
Showing that the subgraph induced on the vertices $a \in V(G)$ such that $z(a) \in H$ for a half-plane $H$ is connected.
Let $G$ be a 3-connected planar graph and $z$ a Tutte embedding. A Tutte embedding is defined as the mapping $z:V(G)\to \mathbb{R}^2$ such that i.) there is a face $F$ of the graph $G$ such that $z$ ...
- 1,030
3
votes
1
answer
185
views
How can I prove that a cactus graph is planar?
I've been struggling with the following question:
Prove that a cactus graph is planar
I've worked out something, but I'm not sure if I'm right or wrong:
Consider every cycle of the cactus graph ...
1
vote
1
answer
224
views
Ultra-Hamiltonian cycle
Ultra-Hamiltonian cycling is defined to be a closed walk that visits every vertex exactly once, except for at most one vertex that visits more than once.
Question:- Prove that it is NP-hard to ...
0
votes
0
answers
424
views
Explanation of proof for planar bipartite graph
I am supposed to prove that a bipartite planar graph has a vertex of degree at most 3.
I saw this answer. But I am little bit confused.
I do not understand the following part:
For planar bipartite ...
- 149
1
vote
2
answers
590
views
Proof that bipartite planar graph has a vertex of degree at most 3
I'm trying to understand proof that bipartite planar graph has a vertex of degree at most 3.
I found this proof: Prove that a bipartite planar graph has a vertex of degree at most 3 .
However, I'm not ...
- 69
1
vote
2
answers
202
views
How to show the following for Planar Graphs-Proof Verification
Please tell me where I am wrong:
Consider this graph $G$:
Show that this graph is not planar.
My answer:
Let us consider the vertices $\{0,1,2,3,4\}$.
Then the sub-graph induced by these vertices is ...
- 1,686
1
vote
5
answers
424
views
How to show that this graph is planar?-Formal Proof
How to show that this graph is planar?
I am unable to write a formal proof
In the book the answer is given that this graph is planar.
Can you kindly say how to prove that this graph has no subgraph ...
- 1,686
0
votes
0
answers
87
views
Are there graphs embeddable on $S^2$ but not on $\mathbb{R}^2$?
The answer is No for finite graphs, of course, via the stereographic projection. But we need a free point on $S^2$ for that to work. Let $\mathfrak{c}$ denote the cardinality of the continuum.
I can ...
- 3,161
9
votes
1
answer
2k
views
All 4-connected planar graphs are Hamiltonian-connected
I started reading Thomassen's paper A Theorem on Paths in Planar Graphs, where he proves one of Plummer's conjectures: Every $4$-connected planar graph is Hamiltonian-connected.
Context. Recall that ...
- 11.3k
4
votes
2
answers
339
views
Adding an edge to a maximal planar graph results in topological minors of both $K_5,K_{3,3}$.
I was trying to prove this exercise from Diestel's book:
Show that adding a new edge to a maximal planar graph
of order at least 6 always produces both a $TK_5$ and a $TK_{3,3}$ subgraph.
I used ...
- 908
0
votes
0
answers
36
views
Regrading segments in planar graphs
I've been reading this paper about linear time planarity testing algorithm. I have a question about two terms authors use throught the whole paper.
What is a segment and what is a subsegment?
I ...
- 1,189