Exercises
Multiple Choice
Articles
Open Problems
Login
13 items
Tagged:
planar graphs
x
Start over
- to expand, or dig in by adding more tags and revising the query.
Sort By:
trending ▼
date
0
Undergraduate
By
Shiva Kintali
on Oct. 4, 2013 | Updated Jan. 4, 2018
Trees and non-planarity
Let \(V\) be a set of vertices, and let \(T_1=(V,E_1)\), \(T_2=(V,E_2)\), and \(T_3=(V,E_3)\) be three trees on the vertices of \(V\) with disjoint sets of edges: …
Mathematics
Graph Theory
planar graphs
trees
0
Undergraduate
By
Shiva Kintali
on Oct. 3, 2013 | Updated Jan. 4, 2018
Planar graphs and girth
Let \(G\) be an \(n\)-vertex simple connected planar graph with girth \(k\). Prove that \(G\) has at most \((n-2)\cdot \frac{k}{k-2}\) edges. Use this to prove that the Petersen graph is nonplan…
Mathematics
Graph Theory
eulers formula
girth
petersen graph
planar graphs
0
Undergraduate
By
Shiva Kintali
on Oct. 3, 2013 | Updated Jan. 4, 2018
Regular planar graphs
Prove or disprove : For each \(n\in \mathbb{N}\), there is a simple connected \(4\)-regular planar graph with more than \(n\) vertices. Prove that a planar, simple, connected, \(6\)-regular graph…
Mathematics
Graph Theory
connectivity
planar graphs
regular graphs
0
Undergraduate
By
Shiva Kintali
on Feb. 12, 2013 | Updated Dec. 6, 2017
Coloring Hamiltonian plane graph
Prove that the faces of a Hamiltonian plane graph can be 4-colored in a such a way that whenever two faces are incident with the same edge they receive different colors.
Mathematics
Graph Theory
graph coloring
planar graphs
0
Undergraduate
By
Shiva Kintali
on June 29, 2012 | Updated Dec. 6, 2017
Coloring Planar Graphs
Prove that every planar graph has at least one vertex of degree at most five. Conclude that planar graphs are six-colorable. Prove that every triangle-free planar graph has at least one vertex of deg…
Mathematics
Graph Theory
eulers formula
planar graphs
0
Graduate
By
Shiva Kintali
on June 7, 2012 | Updated Dec. 6, 2017
Planar Graphs are Pfaffians
Let \(G(V,E)\) be an undirected graph. An orientation of \(G\) is Pfaffian if every even cycle \(C\) such that \(G \setminus V(C)\) has a perfect matching, has an odd number of edges directed in eithe…
Mathematics
Graph Theory
pfaffian
planar graphs
0
Undergraduate
By
Shiva Kintali
on Dec. 3, 2012 | Updated Dec. 6, 2017
Planar graphs and grid minors
Prove that for every planar graph \(G\) there exists an integer \(k\) such that \(G\) is isomorphic to a minor of the \(k \times k\) grid.
Mathematics
Graph Theory
graph minors
planar graphs
0
Undergraduate
By
Shiva Kintali
on Sept. 28, 2013 | Updated Jan. 4, 2018
Crossing number
The crossing number \(cr(G)\) of a graph \(G\) is the lowest number of edge crossings of a plane drawing of the graph \(G\). Prove that the crossing number of \(K_n\) (the complete graph on \(n\)…
Mathematics
Graph Theory
complete graph
crossing number
planar graphs
0
Undergraduate
By
Shiva Kintali
on Jan. 21, 2013 | Updated Dec. 6, 2017
Characterizing outerplanar graphs
A graph is outerplanar if it is isomorphic to a plane graph such that every vertex is incident with the unbounded face. Prove that a graph is outerplanar if and only if it has no subgraph isomorph…
Mathematics
Graph Theory
planar graphs
0
Undergraduate
By
Shiva Kintali
on Oct. 3, 2013 | Updated Jan. 4, 2018
Self-complementary planar graphs
Prove that the complement of a simple planar graph with at least \(11\) vertices is nonplanar. Construct two self-complementary simple planar graphs with \(8\) vertices.
Mathematics
Graph Theory
graph complement
planar graphs
1
2
next page »
icon
Sign In or Sign Up
icon
Invite Friends
Post Something
x
Select What You'd Like To Post
POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Articles
Open Problems
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
formal languages
counting
sorting
optimization
bipartite graph
matching
graph labeling
dynamic programming
adjacency matrix
matrices
Topics
Algebra
Algorithms
Approximation Algorithms
Calculus
Combinatorial Optimization
Combinatorics
Complexity Theory
Data Structures
Discrete Mathematics
Game Theory
Geometry
Graph Theory
Linear Algebra
Linear Programming
Logic
Mathematical Analysis
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×