The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
80 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
23 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
15 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 ...
0
votes
1answer
38 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
23 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
21 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
29 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
46 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
31 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
191 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
65 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
66 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
124 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
48 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.
2
votes
1answer
62 views

Spanning trees in planar dual graph

The amount of spanning trees in a planar graph G is equal to the amount of spanning trees in the dual graph G*. I would like to proove this, i know it's true, but i would like to show that it holds ...
1
vote
0answers
21 views

Planes help please

So I was doing this set of questions: I've done all the questions up to f, but I'm stuck on that. Here's what the mark scheme says, including relevant information needed to do the question So ...
10
votes
1answer
114 views

Which graphs can be drawn using straight lines with no disjoint edges?

What is the class of graphs that can be drawn using only straight lines with no two edges disjoint? Edges are disjoint when they don't cross and they don't share a vertex. Vertices should be in ...
0
votes
1answer
39 views

Determining Planar Graphs

Take a hexagon and add the three longest diagonals. IS the graph obtained this way planar? I'm able to draw the graph very easily. But I don't really understand how to determine what graphs are ...
2
votes
2answers
65 views

Proving corollary to Euler's formula by induction

I'm currently looking at two proofs to the following corollary to Euler's formula and I'm not quite seeing how the authors can make a specific assumption in their proof. One proof comes from my ...
1
vote
1answer
60 views

Is a butterfly network on 8-inputs planar?

I could prove that a four input butterfly network is planar. For that I simply drew it such that no two edges intersect. But I could not use the same approach for the 8-input butterfly network. So I ...
0
votes
0answers
74 views

Prove that a certain graph and its dual are 4-colorable

Let $G$ be a simple planar graph with fewer than 12 faces. Suppose that each vertex of $G$ has degree at least $3$. prove that $G$ and its dual are 4-colorable. I'm not too sure how to approach ...
2
votes
1answer
30 views

Forbidden toroidal minors

A finite graph is planar if and only if it does not have $K_5$ or $K_{3,3}$ as a minor. Is there a (finite) set of minors that can classify if a graph is toroidal?
0
votes
2answers
54 views

Planar complete tripartite graphs

For which values of $r$, $s$, and $t$ is the complete tripartite graph $K_{r,s,t}$ planar? Obviously I want to look for either a $K_5$ or a $K_{3,3}$ in order to show that a specific graph is ...
0
votes
1answer
78 views

Five-coloring plane graphs

These days I've been reading about graph coloring. Right now I'm dealing with the five color theorem. I know how to prove that every planar graph is 6 and 5 colorable. I'm looking on the proof of the ...
2
votes
1answer
64 views

Simple planar graph

What's the best way of proving this? ...
0
votes
1answer
90 views

Finding Number of Edges and Vertices in Icosahedron

This is a practice question from a practice test I am working on. ...
0
votes
0answers
15 views

Find and write the proof of an extension of Euler's theorem for a graph…

Find and write the proof of an extension of Euler's theorem for a graph G(V, E) loop-free with number of vertices v, number of edges e, and number of components k. I think the theorem asked is ...
0
votes
1answer
53 views

Suppose G is an unconnected planar graph, with v nodes, e edges, and f faces, where v ≥ 3.

This is a corollary of Euler's formula. I know the proof for connected planar graphs but I have to prove it for unconnected planar graphs. Suppose $G$ is a connected planar graph, with $v$ nodes, ...
0
votes
2answers
56 views

Let G= (V,E) be an undirected connected loop-free graph.Prove that…

Let G = (V,E) be an undirected connected loop-free graph. Suppose further that G is planar and determines 53 regions. If for some planar embedding of G, each regions has at least 5 edges in its ...
2
votes
3answers
379 views

Prove that Petersen's graph is non-planar using Euler's formula

Prove that Petersen's graph is non-planar using Euler's formula. I know that $n - m + f = 2$. But should I count $f$ and prove that the summation does not equal to two or solve to get $f =7$ and ...
0
votes
1answer
90 views

Planar and Euler's Formula Question

If a connected planar graph has four regions and six vertices, how many edges will the graph have? (I believe the answer is 8 but I'm not positive) 1) 9 2) 8 3) 6 4) 7 Graph A = ({a,b,c,d,e,f,g}, ...
11
votes
3answers
462 views

Can there exist an uncountable planar graph?

I'm currently revising a course on graph theory that I took earlier this year. While thinking about planar graphs, I noticed that a finite planar graph corresponds to a (finite) polygonisation of the ...
1
vote
1answer
40 views

Question on Planar Graph

Let $\delta$ denotes the minimum degree of vertex in a graph. For all planar graphs on $n$ vertices with $\delta\geq3$, which of the following is TRUE? $i)$ In any planar embedding, the number of ...
8
votes
2answers
113 views

Mathematicly Untangeling Untangle.

I have a new addiction, I play Untangle to often, and i am wondering what is the mathematics behind it. some free games: (but be warned highly addictive) Javascript: ...
0
votes
0answers
68 views

Question on Planar graphs

Consider a general planar graph, with no pair of vertexes being joined by more than one edge. Is there a upper limit of planer embeddings of such graph? That is, in how many ways maximum can such a ...
0
votes
1answer
86 views

can someone tell me if this graph contains subdivisions of both K5 and K3,3

Can someone tell me if this graph contains subdivisions of both $K_5$ and $K_{3,3}$ or not? The graph G1134 is non-planar My thought is that this graph subdivision of $K_{3,3}$ but not $K_5$. Is ...
-1
votes
1answer
112 views

non-planar graph question [closed]

The non-planar graph $G$ has degree sequence $$(2, 2, 3, 3, 3, 3, 4, 4).$$ Explain why $G$ cannot contain a subdivision of $K_5$, but must contain a subdivision of $K_{3,3}$. Draw two such a graphs: ...
0
votes
1answer
84 views

What is the maximum number of triangles in a planar graph with n vertices?

The answer is obvious for small numbers of nodes: $$n<3: 0\\ n=3: 1\\ n=4: 3\\ n=5: 5 (see below)$$
0
votes
0answers
94 views

Let $G$ be a simple graph with at least $11$ vertices. Prove that either $G$ or its complement $\overline{G}$ must be nonplanar. Connectivity?

I have seen many solutions to this problem and understand all of them, but I keep thinking they are over simplified because the connectivity of $\overline{G}$ is not addressed. Solutions in general ...
0
votes
1answer
30 views

Planar graph minimum 3 verticies of degree leq 5

Let G be a planar graph with at least 3 verticies. Prove that G contains at least 3 verticies whose degree is $\leq 5$. What i have tried to do: Lets suposse that there exist a planar graph with at ...
2
votes
2answers
43 views

Comparison of almost planar graphs

I have multiple graphs all of which are almost planar. Is there any existing terminology / method which compares them, such that one can say which one is more planar? This could simply be the required ...
2
votes
1answer
40 views

Prove that if $G$ is planar, then $G'e$ is planar too.

I need to prove that if graph $G$ is planar, then a graph created from it by joining two vertices $v,u$ on edge $e$ and connecting to a newly created vertex all others that were connected to either ...
0
votes
0answers
57 views

Why is a connected planar graph isomorphic to its double dual?

Let $G^*$ be the dual graph of a planar graph $G$ (see wikipedia article). How does one prove that if $G$ is connected then it is isomorphic to $G^{**}$?
6
votes
0answers
81 views

Quickest way to solve a matrix one step at a time.

I have a $14\times14$ matrix with a possibility of six states in each position The matrix is random each time. An example matrix would be: $$ \begin{pmatrix} ...
1
vote
1answer
82 views

what is the maximum number of faces with n vertex in planar graphs?

what is the maximum number of faces with n vertex in planar graphs? v=number of vertices f= number of faces for example if v=3 -> max(f)=2 v=4 -> max(f)=4 (a triangle with a point in inner face of ...
3
votes
2answers
182 views

Planar non-3-colorable graphs

Is it true that every planar graph that is not 3-colorable has an even wheel as a subgraph? I'm asking this because I want to prove that every outerplanar graph is 3-colorable.
3
votes
3answers
114 views

Can every simple graph be embedded on a circuit board?

Here, a circuit board is defined as a pair of planar graphs with vertices identified, i.e. a ordered triple $\langle V,E_1,E_2\rangle$ such that there are planar embeddings $h_1,h_2$ for the planar ...
1
vote
0answers
45 views

“Let $G$ be a planar graph. Show that every pair of vertex-disjoint odd cycles in $G^c$ is connected by an edge.” Can't figure out why “odd” matters.

If $C_1,C_2$ are vertex-disjoint cycles in $G^c$, of lengths $m,n$ respectively, not connected by an edge, then their complement has a $K_{m,n}$ minor with $m,n\geq 3$, so $G$ contains $K_{3,3}$ as a ...
3
votes
1answer
131 views

Prove that every dual graph of a planar graph is planar

It seems obvious, but how to prove it properly? I tried Kuratowski, but got stuck at $K_{3,3}$
1
vote
1answer
51 views

Maximum DEgree of a planar graph

If a graph is planar, them what is the maximum degree any of its vertices can have ? Also, can a planar graph have chromatic number more than 4 based on the Vizing theorem ?Isn't vizing theorem a ...