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

6
votes
2answers
427 views

Is there a planar graph that (almost) all its vertices has degree 6?

Is it true that for any $N_0\in\mathbb N$ there exists a planar graph $G=(V,E)$ on (at least) $N_0$ vertices such that at least $$|V|(1-o(1))$$ vertices has degree 6? It is easy to show that no ...
1
vote
1answer
19 views

If edges of $G$ are two colored, then there is a vertex of $G$ with at most two col0or changes in the cyclic order of the edges around the vertex.

Hello there i am reading proofs from the book of Gunter M ziegler. The chapter is called Three applications of eulers formula. Know there is a proposition which i don't fully understand and help would ...
1
vote
1answer
18 views

Find Planar Graph fromVertices and Faces

Could you find a 3-Regular Connected Planar Graph on 10 vertices with 8 faces? If so, explain carefully. I dont know what does regular mean. I think that 3-connected graph on 10 vertices with 8 ...
2
votes
1answer
72 views

Graph theory question about planar graphs

How can i prove that every planar graph can be expressed as a union of five edge-disjoint forests ? I think I should use theorem that says : ' Every planar graph contains vertex with degree 5 or ...
1
vote
1answer
29 views

Triangles formed by line segments in a square

There is a square, denoted by points A, B, C, and D. There are 30 distinct points located inside the square (call these $A_2, A_3, A_4, ... A_{31}$. Non-intersecting segments $A_iA_j$ vertices are ...
4
votes
1answer
61 views

Every simple planar graph with $\delta\geq 3$ has an adjacent pair with $deg(u)+deg(v)\leq 13$

Claim: Every simple planar graph with minimum degree at least three has an edge $uv$ such that $deg(u) + deg(v)\leq 13$. Furthermore, there exists an example showing that 13 cannot be replaced by ...
1
vote
1answer
41 views

Proving the upper bound of edges in a convex polyhedron

The question is the following: Suppose Every face of a convex polyhedron has at least $5$ vertices and every vertex has degree $3$. Prove that if the number of vertices is $n$, then the number of ...
0
votes
2answers
34 views

Can anyone give an example for this theorem related to planar graphs?

Theorem: Let $G$ be a connected planar graph with $p$ vertices and $q$ edges, where $p\geq 3$. Then $q\leq3p-6$. Proof: Let $r$ be the number of regions in a planar representation of $G$. By ...
7
votes
1answer
57 views

Can a planar graph be drawn with all vertices on a straight line?

I have been repeatedly trying to prove and disprove the following: Can any planar graph, with $n$ vertices, be drawn such that the vertices are fixed at coordinates $(0,0)$, $(1,0)$, ..., ...
0
votes
0answers
19 views

Bridges at a non planar graph

Is there any algorithm that gives us the minimum number of bridges we will have to use if a graph is not planar?
0
votes
0answers
31 views

Why is it not possible to draw the $\overline{Q_3}$ in the plane

I am trying to prove that $\overline{Q_3}$ is nonplanar. I know that $Q_3$ is planar and I have attempted to use the corollaries derived from Euler's planarity Theorem to show it is nonplanar but it ...
0
votes
1answer
26 views

Planar graph with V ≥ 2 has at least 2 vertices whose degrees are at most 5

If G was a planar graph on V ≥ 2 vertices. How would I go about proving that G has at least 2 vertices whose degrees are at most 5? I understand that planar graphs can be drawn so that every edge is ...
0
votes
1answer
35 views

Proving if planarity puzzle is planar

An "untangle" game app I have has scrambled planar graphs to be organized by dragging the nodes around until no lines cross. When solved, the puzzle is a lot of triangles. Some nodes have only 2 or 3 ...
1
vote
1answer
28 views

Partitioning a planar graph into spanning trees?

Suppose I have a simple, planar graph, which I want to partition into three edge sets such that each set forms a spanning tree. I've made an attempt at a solution, but it requires a few assumptions ...
0
votes
0answers
13 views

Prove: if G has exactly one $C$-fragment, then there exists a cycle $C$ in a 3-connected graph that is the boundary of a face in $G$.

If G has exactly one $C$-fragment, then there exists a cycle $C$ in a 3-connected graph that is the boundary of a face in $G$. If there is a cycle, then it has to be the boundary of a face (right?). ...
1
vote
2answers
37 views

Edge contraction and subdivision

Let $G$ be a $3$-connected graph that is not homeomorphic to $K_5$ or $K_{3, 3}$. Let $G'$ be the graph obtained from $G$ by contracting an edge. Why is it the case that $G'$ contains no ...
0
votes
0answers
16 views

Why does adding a vertex $x$ that is adjacent every vertex in $G$ with a subdivision in $K_{3,3}$ or $K_5$ result in subdivison of $K_5$ or $K_{3,3}$

Why does adding a vertex $x$ that is adjacent every vertex in a subdivision in $K_{2,3}$ or $K_4$ result in a graph that is a subdivision of $K_5$ or $K_{3,3}$?
0
votes
0answers
27 views

How many edges must you remove from Peterson graph to make it planar

The answer is 2. Why is it not 1? Context: I understand that the Peterson graph is not planar (b/c it contains $K_{3,3}$). What I don't understand is why 1 removing 1 edge doesn't do the job. I've ...
0
votes
1answer
33 views

clarifiying a definition from graph theory more prcisely definition of A-Bridge

I really don't understand this definition from this paper which is: $A-bridge$: if $A \subseteq V(G)$, then an $A-bridge$ of $G$ is either an edge joining two vertices of $A$ or an edge-maximal ...
0
votes
1answer
28 views

G with n vertices is planar if it has most an vertices

“if a connected graph with $n$ vertices has at most $αn$ edges, then $G$ is planar.” For what real numbers $α$ is this statement always true? Prove your answer in both directions. I tried to use ...
1
vote
0answers
46 views

Prove or disprove: If G is bipartite and does not have K3,3 as a topological minor, then G is planar

Prove or disprove: If G is bipartite and does not have K3,3 as a topological minor, then G is planar. I really have no idea how to do this...
0
votes
0answers
61 views

A plane triangulation is 3-connected: Proof

I want to prove: "A plane triangulation $G$ with at least 4 vertices is 3-connected" I have found this proof. I don't like it but I took some ideas out of it: ...
1
vote
0answers
13 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 ...
2
votes
0answers
20 views

Does every polyhedral graph have a path cover with non-empty paths?

I'm looking to prove or disprove the following conjecture: Every polyhedral graph has a path cover with vertex disjoint, non-zero (length $\ge 1$) paths. Any pointers to literature are appreciated. ...
0
votes
1answer
23 views

Planarity Criterion

I am looking for a proof of the theorem: If a planar graph, $G$, has $v$ vertices ($v \geq 3$) and no cycles of length 3 then, $e \leq 2v-4$. I remember doing this in a graph theory course and I ...
1
vote
1answer
47 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 ...
0
votes
0answers
11 views

Embeddings of a $2$-connected planar graph

Suppose, I have the adjacency matrix of a $2$-connected planar graph. The embedding might not be unique. How can I find out which embedding (or embeddings) the graph has without drawing it ? The ...
4
votes
0answers
27 views

Is this the smallest graph with the desired properties?

The above graph has the following properties : $1$) Every vertex is start vertex of some hamiltonian path. $2$) It contains no hamiltonian cycle. $3$) It has no cycle of length $3$. $4$) It is ...
1
vote
0answers
46 views

Convex planar graphs

A planar graph is called convex, if it can be drawn in a way such that every face, including the outer face is convex. Wikipedia states that a planar graph is convex if and only if it is a ...
1
vote
1answer
153 views

A space curve is planar if and only if its torsion is everywhere 0

Can someone please explain this proof to me. I know that a circle is planar and has nonzero constant curvature, so this must be an exception, but I am a little lost on the proof. Thanks!
1
vote
1answer
69 views

Cycles and faces in planar graphs

Let G be a connected planar graph. Supopose, we know all cycles of G. Is this enough to determine the length of the face boundaries ? In particular, are the lengths of the face boundaries unique ...
1
vote
0answers
31 views

Which sequences $d_1,\ldots,d_n$ guarantee the planarity of a graph?

Which sequences $$d_1,\ldots,d_n$$ $$d_1\le \cdots\le d_n$$ have the property, that every graph with this degree sequence is planar ? It is clear that every sequence with $d_n\le 2$ works. As for ...
1
vote
0answers
14 views

Which degree sequences $d_1,…,d_n$ are planar-graphical?

Which degree sequences are planar-graphical, that means for which degree sequences $$d_1,...,d_n$$ $$d_1\le...\le d_n$$ exists a PLANAR graph that has this degree sequence ? I found some links in ...
1
vote
0answers
25 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. ...
2
votes
1answer
47 views

Is there a $4$-regular planar self-complementary graph with $9$ vertices and $18$ edges?

Recently, a user asked for the construction of regular self-complementary graphs. I found the graph consisting of the hamilton-circles $$1-5-8-3-9-6-2-4-7-1$$ and $$1-3-5-2-9-4-8-7-6-1$$ with ...
0
votes
0answers
95 views

Proof that a planar graph is eulerian if and only if the dual graph is bipartite

I need the proof that a planar graph is eulerian(a graph that has eulerian tour) if and only if the dual graph is bipartite. Can someone help?
0
votes
1answer
130 views

3-regular connected planar graph

Let $G$ be a 3-regular connected planar graph with a planar embedding where each face has degree either 4 or 6 and each vertex is incident with exactly one face of degree 4. Determine the number of ...
2
votes
0answers
47 views

Graph planarity and electronic circuit boards

In another MSE question, I found the following definition for 2-layer circuit board decomposition of a graph: A circuit board is defined as a pair of planar graphs with vertices identified, i.e. ...
0
votes
1answer
87 views

How would I find the scale factor of a dilated figure on a coordinate plane?

The above question is pretty simple, and I used common sense to figure out that the coordinates (3, -7) is the answer, since it is the only viable spot. I was wondering how I would find the scale ...
1
vote
1answer
125 views

3-regular planar graph

Yet another question I was going over and struggled. Given a 3-regular connected planar graph, so that every vertex lies on the edge of a face of length 4, of a face of length 6 and of a face of ...
-1
votes
1answer
30 views

Trouble determining planarity of graph

I am practicing for an exam and I can not wrap my head around this exercise. I am supposed to show if the given graph is planar by drawing it or show the subgraph that is homeopathic to K 3,3 or K5. ...
1
vote
1answer
34 views

Determining if a graph is planar and if so draw or disprove with Kuratowski's Theorem

This is a practice exercise for in my text that even my professor was having trouble explaining to me. The instructions are in the title. Here is an image of the graph: I believe this graph is not ...
0
votes
0answers
43 views

A planar graph has either 2 faces or 2 vertices of degree less than 3

Practicing for an upcoming test, I stumbled upon this question: A planar graph with at least three vertices has either 2 faces of length at most 3, or 2 vertices of degree at most 3. Which is a ...
0
votes
1answer
86 views

Proof for binary tree is a planar graph

Suppose G is a binary tree. Is G necessarily planar? Give a proof, or a counterexample. My guess is that it is indeed planar but I am struggling to find a formal proof for this. EDIT: Is there a ...
1
vote
1answer
34 views

Number of maximal planar subgraphs

Suppose we have an undirected graph $G$ which is maximal planar, i.e. adding an edge results in $G$ not being planar anymore. How many subgraphs $G'$ does $G$ have such that $G'$ is also maximal ...
8
votes
2answers
246 views

Visual illustrations of circle packing theorem?

Circle packing theorem states: For every connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G. Paper Collins, Stephenson: A circle ...
1
vote
1answer
99 views

Graph Theory Question On Exam Involving colorability of certain planar graph

I had a question on my exam and answered it using what I believe to be an Exhaustive Proof. The teacher marked it wrong, and while I understand there is a simple answer to the question, I would like ...
0
votes
0answers
111 views

Thickness of G when G is a simple connected graph

The thickness of a simple graph G is the smallest number of planar subgraphs of G that have G as their union. Show that if G is a connected simple graph with v vertices and e edges, where v ≥ 3, then ...
1
vote
2answers
598 views

Show that planar graph has at least 4 nodes of degree 5 of less

I am having a problem with this assignment. So the task says: ...
0
votes
3answers
60 views

Planar Graph max min edges

Consider a planar graph with 5 vertices, what is the minimum and the maximum number of edges such a graph can have? The graph need not be connected and is simple.