A planar graph is a graph (in the combinatorial sense) that can be embedded in a plane. In other words, there is some pictorial representation of the graph such that the edges only intersect at vertices. Consider tagging with (combinatorics) and (graph-theory).

learn more… | top users | synonyms

0
votes
0answers
9 views

Example of planar representation of Bipartite graph

Give an example of planar representation of Bipartite graph ($K_m,_n$) that has $\left\lfloor \frac m2\right\rfloor \left\lfloor \frac n2 \right\rfloor \left\lfloor \frac {m-1}2\right\rfloor ...
2
votes
0answers
29 views

Planar representation of $K_m,_n$

Crossings in the graphic representation of some graphs. Give a planar representation of $K_m,_n$ that has $\lfloor \frac m2\rfloor \lfloor \frac n2 \rfloor \lfloor \frac {m-1}2\rfloor \lfloor \frac ...
0
votes
0answers
16 views

Number of non-isomorphic embeddings.

Define two embeddings of a graph on a surface to be non-isomorphic if their corresponding dual graphs are non-isomorphic. How many distinct embeddings (up to isomorphism) are there of a $3$-regular, ...
1
vote
1answer
23 views

Minimal 4-regular planer graph

I'm asked to draw a minimal 4-regular planer graph and to give number of its verteces and edges. I tried Octahedral graph (see picture) with 6 verteces and 12 edges, but it doesn't work. I'm not sure ...
1
vote
1answer
19 views

How do I create a minor of a $K_5$ or $K_{3,3}$ configuration from this $10$ vertex graph?

I have a graph with $10$ vertices, all of which are degree $3$: I am trying to show it is either planar or nonplanar, so I use the circle-chord method to create a circuit $abcdefghija$ (easy since ...
1
vote
2answers
14 views

Complete bipartite graph from 2 to m points

How can I show that $K_{2,m}$ is planar for all m? I can't even seem to draw $K_{2,2}$ without intersection and if I draw it as a square then it seems to fail to be bipartite as the second set lies ...
1
vote
1answer
14 views

Number of faces of connected plane graph with cycles

Suppose $G$ is a connected plane graph with at least $g$ edges containing no cycles of length smaller than $g$, then if $f$ is the number of faces and $e$ is the number of edges then prove that $f ...
0
votes
0answers
16 views

Let $G$ be a planar graph. Suppose that $V = V_4 \cup V_8$. Prove that if $|V_8| = 12$, then $|V_4| \ge 18$

For each $n \in \mathbb N$, define $$V_n = \{v \in V : d(v) = n\}$$ Proof. Let $G = (V, E)$ be a planar graph. Suppose that $V = V_4 \cup V_8$. Suppose that $|V_8|$ = 12. Since $|V_8| = ...
1
vote
0answers
22 views

Let G be a simple planar graph such that the length of every cycle is at least 8. Show that $|E| \le \frac{4}{3}|V| - \frac{8}{3}$

Here's what I've got so far. I'm stuck on how to proceed. I believe I need to plug back into Euler's formula, but I'm not getting what I'm looking for by doing that. Where is the denominator of $3$ ...
0
votes
1answer
10 views

Find a crossing-free planar embedding of this graph?

I've been spending far too long on this problem. I need to find a crossing-free planar embedding of this graph: If there's a slight trick to it on what edge to move first, I'd prefer a hint ...
6
votes
1answer
49 views

Given a graph $G$ with $7$ vertices, either $G$ or its complement must be planar.

Given a graph $G$ with $7$ vertices, either $G$ or its complement must be planar. The closest thing to this question that I've found on the internet is this but since it uses Euler's formula, I ...
4
votes
2answers
92 views

What is a “map” in the four color theorem?

The four color theorem declares that any map in the plane (and, more generally, spheres and so on) can be colored with four colors so that no two adjacent regions have the same colors. However, it's ...
0
votes
0answers
29 views

Planar 8-graph with 11 edges where every face is bounded by at least 5 vertices

The title says it all - I'm currently working my way through a book about discrete mathematics and I'm stuck on either proving or disproving the existence of a planar graph with 8 vertices and 11 ...
3
votes
1answer
64 views

Prove that the tesseract graph is non-planar

The tesseract graph may be defined in various ways; I'm thinking of it as a subset lattice of the set {a,b,c,d}, where two subsets are adjacent if they differ in size by one, and one contains the ...
2
votes
0answers
85 views

Let $n \ge 6$. Prove that it is not possible to partition the edges of $K_n$ into floor($\frac{n}{6}$) planar subgraphs. [duplicate]

Any hints will be appreciated. Here are some things I thought about: Since $K_n$ is a complete graph, it must be $(n - 1)$ regular The sum of the degree of all its vertices is $n(n - 1)$ There are ...
1
vote
1answer
85 views

Partitioning the edges of $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs

Why is it impossible to partition the edges in $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs for $n \ge 6$? I'm just stuck at the beginning and can't figure out how to go about this problem. ...
0
votes
1answer
64 views

Counting edges in a finite connected graph where each vertex is exactly one of two values.

Let $p,q$ and $r$ be positive integers greater than $0$ with $q\neq r$. Suppose that $H$ is a finite connected graph without loops or multiedges on $p$ vertices with $q$ vertices of degree $r$, $r$ ...
1
vote
1answer
29 views

Connected Planar Graph

In a connected planar graph, every vertex has degree $3$, and every face is bordered by $5$ or $6$ edges. How many faces are bordered by $5$ edges?
0
votes
2answers
46 views

Extending Kuratowski's planarity theorem on finite graphs to countable infinite graphs.

As the title suggests. Kuratowski's theorem states that a graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_3,_3$ I want to extend this result to "A infinite graph G ...
0
votes
1answer
20 views

Hamiltonian cycle that contains a specified edge in a 3-connected cubic bipartite planar Hamiltonian graph

Assume that we have a 3-connected cubic bipartite planar graph with a Hamiltonian cycle. That graph must have at least 4 Hamiltonian cycles, because of Theorem 1 and Theorem 10 of this paper. I would ...
0
votes
0answers
27 views

Last portion of Kuratowski's theorem

I refer to the proof of Kuratowski's theorem for 3-connected graphs in Diestel. I have a question about the last portion (page 82), about embedding $y$ within the face $f_i$ bounded by the cycle $C = ...
1
vote
1answer
63 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 ...
2
votes
1answer
40 views

Kempe's proof of the four colour theorem

What exactly was Kempe's error in his proof of the four colour theorem? What I understand of his general idea is by the following case: Suppose an uncoloured "country" is surrounded by countries of ...
1
vote
1answer
31 views

Boundary of faces of plane graph

Theorem. Let $G$ be a plane graph with at least 3 edges drawn on $\mathbb{R}^2$. Then every face of $G$ is bounded by at least 3 edges. We define vertices to be points in $\mathbb{R}^2$ and an ...
-1
votes
2answers
90 views

four color theorem proof? [closed]

I need a proof of four color theorem of planar graph. Here Any equivalent to the Four color theorem for non-planar graphs? given that chromatic number is up to minimum degree plus one, but I've seen ...
1
vote
1answer
58 views

How do you prove a graph **is not** planar? [duplicate]

Is there a theorem using the number of edges and vertices, or something about the max degree a vertex can have? I know that you can use $e ≤ 3v−6$. But what if that condition holds, and it still might ...
1
vote
1answer
29 views

Scalene rectangulation of a square: let me count the ways

A rectangulation of a square is a dissection of the square $S$ into smaller rectangles $R_i$, $i=1,\ldots,n$ with the usual caveats: $S = \cup_i R_i$ and the interiors of distinct rectangles ...
1
vote
2answers
86 views

Kuratowski's Theorem and Planar Graphs

Suppose there is a non-planar graph $G$ with $E$ edges and $V$ vertices, and that $G-e$ is planar for every edge $e$ of the graph. I am asked to show that $E-V=3$ or $E-V=5$. I know that I am supposed ...
1
vote
1answer
38 views

Converting all arcs to polygonal arcs in a plane graph

I am trying to understand a proof on the conversion of arcs to polygonal arcs in plane graphs, in the book "Graphs on Surfaces" by Mohar and Thomassen. In the book, an arc joining two points $x,y \in ...
3
votes
1answer
89 views

The Four Ways to Arrange Squares in Barnette Graphs

Below you see an example of a bicubic graph consisting of faces with degree $4$ and $6$, which makes up the set of graphs of my interest and is a subset of the so called Barnette graphs. ...
3
votes
1answer
109 views

Number of faces in a planar graph bounded by odd length cycles?

Suppose that every face in a planar graph is bounded by odd length cycles, then the number of faces of this planar graph is even. I want to prove this using Euler's formula, but not really sure where ...
4
votes
1answer
80 views

Use Gröbner bases to count the $3$-edge colorings of planar cubic graphs…

I found a nice introduction on how to Use Gröbner bases to construct the colorings of a finite graph. Now my graphs $G=(V,E)$ are the line graphs planar of cubic graphs, so they are $4$-regular. The ...
0
votes
0answers
14 views

Decomposing a graph into $N$ planar sub-graphs that can be drawn on $N$ planes.

I would like to ask you if there is a way for checking if we can decompose a specific graph into $N$ planar sub-graphs that can be drawn on $N$ planes without an edge crossing any of the planes.
0
votes
0answers
12 views

Complement of a hamiltonian circuit in a 4-valent simple planar graph

Consider a 4-valent simple planar graph G. Suppose that it has no vertices which if removed would disconnect the graph. It has been proven that such a graph has a Hamiltonian circuit. It is also ...
0
votes
2answers
58 views

Each regional of a maximal planar graph is a triangle

Show that every region of a maximal planar graph is a triangle. A planar graph G is called maximal planar if the addition of any edge to G creates a nonplanar graph. Will this proof use the ...
1
vote
1answer
126 views

How to count the closed left-hand turn paths of planar bicubic graphs?

When you draw a planar cubic bipartite graph $\Gamma$ and 3-color its edges you can use this as an orientation $\mathcal O$. Definition A left-hand turn path on $(\Gamma, \mathcal O)$ is a closed ...
2
votes
1answer
44 views

finding edges of a triangle graph from degrees of points

my theory: Given a list of points on a 2 dimensional plane, and the degree of each point, there should correspond only one way to arrange the edges between points so that the final graph is a mesh of ...
1
vote
0answers
34 views

Abstract dual of a graph and $K_{3,3}$

Let $G$ be a graph. The abstract dual of $G$ can be defined as a graph $G^*$ whose edges are in one to one correspondence with $G$ and whose spanning trees are obtained by taking the complements of ...
1
vote
0answers
22 views

Automorphism group of planar graphs

I am going through Constructive Approach to Automorphism Groups of Planar Graphs by Klavík et al. It has shown that the automorphism group of a planar graph $G$ is as follows. $$ \text{Aut} ...
0
votes
0answers
33 views

Kuratowski's theorem proof: Flappable bridges

I have a doubt concerning the proof of Kuratowski's theorem. The proof I am reading from is from Combinatorial Problems and Exercises by Lovasz. (Pg 299-301). We are given a graph $G$ which is a ...
1
vote
1answer
33 views

$G$ a maximal simple planar graph with $n$ vertices, $m$ edges and $ki$ vertices of degree $i$. Show that $\sum_{i= 1}^{n-1}(6-i)k_i = 12$.

$G$ is maximal simple planar graph with $n$ vertices and $m$ edges. There are $ki$ vertices of degree $i$, for $i = 1, \dots, n-1$. Show that $\sum_{i= 1}^{n-1}(6-i)k_i = 12$. I got the following ...
3
votes
0answers
58 views

Automatic solver of four-color theorem? [closed]

Does anyone know of an app/online tool to automatically colour any map or image using the 4-colour theorem? (Taking a Black and white image as input).
1
vote
1answer
34 views

How to find a planar graph if I know that it has 7 faces with certain sizes?

I can't figure out how to find a graphs with this properties: I have to find 2 non-isomorphic plane graphs which (each of them) have 7 faces, two of which are of size 3 and the rest of size 4. This ...
1
vote
1answer
33 views

Maximum number of edges of a planar graph without cycles of length 3 and 4

I'm trying to calculate the maximum number of edges in a planar graph without cycles of length $3$ and $4$ (thus, $C_3$ and $C_4$). I've assumed that the condition is that the length of each face has ...
1
vote
1answer
92 views

Highest possible number of edges in a planar graph, which does not contain C3 or C4

Determine the highest possible number of edges in a planar graph, which does not contain C3 or C4 (C = cycle, 3,4 = length of the cycle). Details: you are given $n$ vertices and they are asking you ...
5
votes
1answer
112 views

A doubt in the proof of Kuratowski theorem

In trying to understand the proof of Kuratowski's theorem (namely, a graph is planar if and only if it contains no subdivision of $K_5$ or $K_{3,3}$) from this book (Page 299) I am first trying to ...
0
votes
0answers
24 views

Result of LexBFS on an outer-planar graph

Suppose we have an outer-planar graph $G$. Is the following expression true? If yes, please prove it. If no, please give a counterexample. After running LexBFS on $G$, we will have a vertex order ...
3
votes
2answers
53 views

Guaranteeing a path is on the outer face of a planar graph

Let $G$ be a planar graph containing a path $P$. Is it always possible to draw $G$ in the plane so that the path is on the outer face? If the path consists of a single edge then one can use ...
0
votes
0answers
17 views

Prove that if $G$ is planar graph with $\delta(G) \geq 3$ and less than $12$ faces, then its girth is less than $4$

I'm not really sure how could I use the fact that $\phi(G)$ < 12. Since $\delta(G) \geq 3$ I have: $2e(G^*)= 2e(G) \geq 3|G|$ where $G^*$ is dual graph, so: $\sum_{f \in F(G)} deg(f) \geq ...
0
votes
0answers
29 views

What is the definition of Planar $3$-Sat problem?

I have some steps in my lecture-notes to make an instance of Planar $3$-Sat problem from an instance of $3$-Sat problem. The steps are as follows: Create one vertex for every literal $x_i$ Create ...