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
1answer
23 views

Are all connected graphs with Euler characteristics 2 planar?

I have read proofs and descriptions stating that a planar connected graph have the Euler characteristic 2. I'm not sure if that statement is equivalent to "a connected graph with the Euler ...
0
votes
1answer
36 views

$ G=(V,E_1 \cup E_2) $ is a triangle free graph, where $ G_1=(V,E_1) $ is planar and $ G_2 = (V, E_2)$ is a tree. Prove that: $ \chi (G) < 7 $

can anyone help with this, any direction could be helpfull? I've tried using the fact that $ G_1 $ satisfies that it's planar and is triangle free because G is. So we should have $|E_1| \leq 2|V|-4 $ ...
0
votes
0answers
16 views

Translating position of x y onto new plane

I have two planes, both the same size, one directly in front of the other - plane A is in front and is 200 x 200, plane B is behind and is also 200 x 200. When I draw a line or rectangle or whatever ...
2
votes
1answer
103 views

Simple connected plane graph G and its dual graph G*; if G is isomorphic to G*, then G is not bipartite?

Let $G$ be a simple connected plane graph where $v>2$, and $G^*$ is its dual graph. Prove that if $G$ is isomorphic to $G^*$, then $G$ is not bipartite. I know that $G$'s number of faces is ...
2
votes
1answer
40 views

Planar graph and number of faces of certain degree

Let G be a 4 regular connected planar graph (with a planar embedding), where all faces are either degree 3 or degree 4. Then determine the number of faces of degree 3. Also, now suppose that every ...
3
votes
1answer
46 views

Prove that the graph dual to Eulerian planar graph is bipartite.

How would I go about doing this proof I am not very knowledgeable about graph theory I know the definitions of planar and bipartite and dual but how do you make these connection
0
votes
1answer
23 views

In graph theory, what's the difference of triangles and 3-faces?

I'm pretty sure that triangles and 3-faces are not the same but I cannot find their differences according to their definitions. Could you please help me with that? Thanks
2
votes
2answers
55 views

A planar graph on $n \geq 3$ vertices has at most $3n-6$ edges: is the converse true?

I know by Euler's formula that if $G=(V,E)$ is planar on $n \geq 3$ vertices, then $|E|\leq 3n-6$. Is the converse true? If not, how to prove that le cube below is planar ?
2
votes
2answers
27 views

Why is every repeated vertex in the walk around the outer face of a finite planar graph a cut vertex?

Let G be a finite planar graph, then there is a natural walk around the outer (i.e. the unbounded) face of G. It might happen that a vertex v is visited more than once by this walk. Proof that this is ...
0
votes
0answers
33 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
26 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
155 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
30 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
27 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
90 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
19 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
27 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
37 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
47 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
39 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 ...
-1
votes
0answers
21 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
20 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
32 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
84 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
33 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
65 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
48 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
44 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
78 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
224 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
95 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
23 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
490 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
37 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
41 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
101 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
46 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
118 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
50 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
40 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
83 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
31 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
53 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
75 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
74 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
19 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 ...