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
26 views

Complete Planar Bipartite Graph

Determine exactly the values of $m$ and $n$ for which the complete bipartite graph $K_{m,n}$ is planar. I have tried doing this by drawing different complete bipartite graphs and just using guess and ...
1
vote
1answer
23 views

Determine all graphs with size $3n-5$ such that $G-e$ is planar for every edge $e$ of $G$.

I believe I have this one, but I wanted to see if my reasoning is sound since I can only find 1 such graph with this property. Let $G$ be a graph of order $n$. First, if $G-e$ is planar for every ...
3
votes
2answers
146 views

Showing planarity of graphs

I am trying to show $G_3$ is planar. I have constructed $G'_3$ as shown. Is it correct to say that by the Jordan curve theorem, $G_3$ cannot be planar, as any drawing will cause edges to overlap. ...
1
vote
1answer
24 views

Decide if this cubic graph on 8 vertices is planar

Because I couldn't count faces and carry out Euler's formula for planar graphs I decided to "find" the $K_{3,3}$ subgraph in this way I'm not sure is how we're supposed to do it. Given this graph ...
0
votes
1answer
22 views

Every graph of degree 2 is planar

A graph is planar if it can be drawn on flat paper so that no lines cross each other. Suppose G is a component where every node has degree 2, and no node in G has arc to itself. Is G ...
1
vote
0answers
75 views

The skeleton of Eulerian polyhedra

There is (at least) two kind of validity domain of Euler's $v−e+f=2$ polyhedron formula. One is the "Eulerian" polyhedra, i.e. simply connected polyhedra with simply connected faces (see here). The ...
0
votes
0answers
15 views

Pairwise crossing lines meaning

I'm having a hard time being certain of the meaning "pairwise crossing" in the context of Graph Theory... namely, if say 4 lines are pairwise crossing, may any be parallel. the question states: "A ...
1
vote
0answers
20 views

Analogue of Fáry's theorem taking sphere and geodesics instead of plane and straight lines.

Fary's theorem states that any simple planar graph can be drawn without crossings so that its edges are straight line segments (see Wikipedia). The proof is based on the Art gallery theorem, so I ...
2
votes
1answer
31 views

Dual graph of a tree

It is stated here that: For any connected embedded planar graph G define the dual graph G* by drawing a vertex in the middle of each face of G, and connecting the vertices from two adjacent ...
2
votes
2answers
45 views

Give a formal argument why there is no planar graph with ten edges and seven regions. Here is my answer

I'm really new to a graph theory, and I have to answer the following question: give a formal argument why there is no planar graph with ten edges and seven regions. Here is my answer: Using ...
1
vote
1answer
34 views

Approach to determining if a graph is planar by inspection/kuratowski's theorem

I'm taking an intro discrete math course and am having trouble determining if a graph is planar or not. When proving a graph is planar, if Euler's formula doesn't apply I just randomly redraw the ...
0
votes
0answers
18 views

Can someone advice edge contraction tool?

I need to show how edge contraction happening in graphs and the best way for it is visual presentation. Maybe someone can give an advice about a tool where it can be simply represented. Maybe a ...
0
votes
0answers
18 views

Left-Right planarity Testing for Petersen graph

Could somebody tell me how to use the signed constraint of the left-right planarity criterion to show Petersen graph is not planar?
0
votes
0answers
25 views

An example of a DFS-oriented graph

Could somebody give an example of a DFS-oriented graph with a non-aligned LR-partition such that the corresponding LR-ordering does not yield a planar embedding?
0
votes
1answer
58 views

What is a graph that contains subdivision but not minors and vice versa?

I am looking for graphs which satisfy the following conditions. (I have tried finding some possible solutions but no way to confirm them) (a). a K5 as a minor but no K5-subdivision? ans. Petersen ...
0
votes
1answer
31 views

An example for a planar graph with different embeddings with different degree sequences of the faces?

Let $G$ be a planar graph with a planar embedding with $f$ faces. The degree of a face $f_i$ is the number $a_i$ of edges that are incident to $f_i$ (counting bridges twice). Assume that the faces ...
3
votes
2answers
60 views

Crossing of strings

There are two strings of color red and blue. They are made to cross each other odd number of times (greater than one) without any self crossing. Is it always possible that there will be pair of ...
1
vote
3answers
63 views

$K_{3,3}$ an exception to Planar Graph formula

So I have learned that for a graph to be considered Planar, if it has at least 3 vertices, you can apply the following formula to test for planarity: number of edges ≤ 3(number of vertices) - 6 also ...
0
votes
1answer
43 views

Prove: If $G$ is a planar graph with $p$ vertices, $q$ edges, and finite girth $g$ then, $q \leq \frac{g(p−2)}{g−2}$ .

Prove the following theorem: If $G$ is a planar graph with $p$ vertices, $q$ edges, and finite girth $g$ then, $$q \leq \frac{g(p−2)}{g−2}$$ . I do not know how to go about proving this, besides the ...
0
votes
1answer
34 views

What is the maximum number of edges you can add to the wheel Wn and still obtain a planar graph?

What is the maximum number of edges you can add to the wheel Wn and still obtain a planar graph? I know that the outside of the wheel can always be a cycle of 3 and that W4 has max edges=6, W5=9, ...
1
vote
1answer
53 views

Graph theory question(about planar graphs, degrees)

Prove, that every planar graph, which has no loops or multiple edges, and has more than 3 vertices(it can be 3 too), has at least 3 vertices, which have 5 or less degree. I kinda can't start this, I ...
2
votes
3answers
182 views

Every planar graph can be embedded on a sphere - formal proof?

The proof of the following theorem: A graph can be embedded on the surface of a sphere without crossings if and only if it can be embedded in the plane without crossings. is very short- The ...
3
votes
1answer
91 views

Every polyhedral graph is planar - proof

Every graph theory book or internet resource on graph theory says the graph of a convex polyhedron is planar, i.e. it can be drawn on a plane without edges crossing. Graph of a convex polyhedron is ...
-1
votes
1answer
22 views

Prove concerning planar graph

I need to prove that in a planar graph with more than two vertexes at least a vertex with a maximum grade of five exists. I know that planar graphs fulfill the relation $\#E \le 3\#V-6$, and relation ...
6
votes
2answers
472 views

Is there a planar graph that (almost) all its vertices have 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
32 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
37 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
92 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
39 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 ...
5
votes
1answer
104 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
47 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
39 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
74 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
20 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
33 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
28 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
42 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
52 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 ...
1
vote
2answers
50 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
18 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
1answer
38 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
30 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
51 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...
1
vote
0answers
15 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
22 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
57 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
14 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
48 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 ...