# Questions tagged [planar-graphs]

A planar graph is a graph (in the combinatorial sense) that can be embedded in a plane such that the edges only intersect at vertices. Consider tagging with [tag:combinatorics] and [tag:graph-theory]. For embeddings into higher-genus spaces, use [tag:graph-embeddings].

1,008 questions
Filter by
Sorted by
Tagged with
48 views

### Maximum number of vertices with degree three in maximal bipartite planar graphs

A bipartite graph $G$ is a graph where each cycle has an even length. If $G$ can be drawn on the plane without any crossings of edges, $G$ is called planar. $G$ is called maximal planar bipartite if ...
35 views

### Inductive proof for statement about product of weights in intro to dimer model

I was reading this review by Kenyon on the dimer model, and there's a lemma at the beginning that I'm struggling to prove. Here's the set-up. We have a finite 2D square lattice graph, bounded by a ...
1 vote
33 views

1 vote
14 views

### Related between Kuratowski theorem and any graphs that $\chi(G)\leq 4$ and $\chi(G)\leq 5$

Is there related between Kuratowski's theorem and any graphs that $\chi(G)\leq 4$ and $\chi(G)\leq 5$ (chromatic number)?
86 views

### Construct a class of maximal planar graphs with exactly 4 vertices of degree 3.

The post is very interesting, and it tells us that any planar graph with at least $4$ vertices has at least $4$ vertices of degree $5$ or less. Recently, I also saw a question on a Chinese forum (...
38 views

### e <= 3v - 6 for planar graph question: why does every face (of a planar graph) have to have at least three sides?

Can't we make a face with just two edges(sides) and two vertices? We just connect those two vertices twice each with different edges and we can make a face between the two edges with only two vertices ...
82 views

### Could there exist a planar graph with the following degrees of vertices: {5, 5, 4, 4, 4, 2} [closed]

I was wondering if a graph existed because I used euler's inequality and it said that theres supposed to be a graph but im having a hard time figuring out what it is. Thank you!
1 vote
32 views

### Asymmetric graphs with asymmetric edge-deleted subgraphs

When I say graph, I mean undirected, irreflexive graphs without multiple-edges (sometimes called a simple graph). Call a graph $G$ “asymmetric” if the only automorphism of $G$ is the identity map. For ...