All Questions
Tagged with planar-graphs bipartite-graphs
36
questions
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$...
1
vote
0
answers
55
views
Let $n\geq 3$. Is there a connected, planar, bipartite graph with $n$ regions and $n$ vertices?
The answer given is that according to a Corollary of Euler’s formula (Corollary 3 Section 10.7), such a graph has at most $2n − 4$ edges. Applying this to Euler’s formula ($r = m − n + 2$), there are ...
- 11
1
vote
1
answer
227
views
Is a maximal planar bipartite graph containing cut vertices isomorphic to a star?
A simple graph $G$ is called maximal planar bipartite if it has the property: if we add an
edge (without adding vertices) to $G$, we obtain a graph which is no longer planar, bipartite or simple.
See ...
- 2,474
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
573
views
Prove Herschel graph is nonhamiltonian
Let us denote by $c(G)$ the number of components of graph $G$.
Theory: For a hamiltonain graph we have $c(G-S)\leq|S|$ for any set $S$ of vertices of $G$.
How can I show that Herschel graph is ...
2
votes
1
answer
613
views
A non planar graph has either five vertices of degree at least 4 or six vertices of degree at least 3 (Without using Kuratowski's theorem)
This was given as an exercise in my textbook before Kuratowski's theorem (a graph is non planar if and only if it has a subgraph homeomorphic to K$_5$ or K$_{3,3}$) was even introduced. So, there must ...
- 174
3
votes
1
answer
255
views
Largest Planar Subgraph of a Bipartite Graph
The maximum planar subgraph problem (i.e given a graph, find its subgraph which is planar and has the maximum number of edges) is NP hard and MaxSNP hard (as per wikipedia) and we do not have a ...
- 133
1
vote
0
answers
58
views
Is there any new developments on the Barnette's conjecture?
When I searching for interesting math problems. I find there is a graph theory conjecture called the Barnette's conjecture.
The statement is: Is every bipartite simple polyhedron Hamiltonian?
A early ...
- 178
0
votes
0
answers
53
views
NP-completeness of bipartite planar graph problem
I want to know whether a certain graph problem is NP-complete or not. The problem is as follows.
Given an undirected planar bipartite graph with in every vertex a number. Can you make a subgraph for ...
- 23
0
votes
0
answers
570
views
Number of faces in Bipartite simple graph
Prove that the number of faces of a simple bipartite graph on 3 vertices is 4 faces?
The number of edges in a planar bipartite graph of order $n$ is at most $2n-4$.
Proof: Let G be a planar bipartite ...
- 1,189
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
4
votes
1
answer
259
views
Two from Cubic Subgraph Hardness
The Problem
For a given graph $G$, the cubic subgraph problem asks if there is a subgraph where every vertex has degree 3.
The cubic subgraph problem is NP-hard even in bipartite planar graphs with ...
1
vote
1
answer
442
views
Existence of 3-regular connected bipartite planar graphs of order 14
I'm struggling with finding 3-regular, connected bipartite planar graphs on 14 vertices.
I tried starting with a cycle on all vertices but I couldn't quite get a planar graph.
Can someone help?
- 75
2
votes
1
answer
483
views
Proving Graph Theory Question
I am not able to come up with a proof regarding this statement -
Consider G be a connected planar graph. If G is not bipartite, then any planar embedding of G has at least 2 faces with odd degree.
Can ...
- 83