Tagged Questions

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).

19 views

A connected $k$-regular graph of order 12 is embedded in the plane, resulting in eight regions. [on hold]

A connected $k$-regular graph of order $12$ is embedded in the plane, resulting in eight regions. What is $k$?
23 views

23 views

Number of non-isomorphic embeddings.

Define two embeddings of a graph on a surface to be non-isomorphic if their corresponding dual graphs are non-isomorphic. How many distinct embeddings (up to isomorphism) are there of a $3$-regular, ...
27 views

Minimal 4-regular planer graph

I'm asked to draw a minimal 4-regular planer graph and to give number of its verteces and edges. I tried Octahedral graph (see picture) with 6 verteces and 12 edges, but it doesn't work. I'm not sure ...
25 views

How do I create a minor of a $K_5$ or $K_{3,3}$ configuration from this $10$ vertex graph?

I have a graph with $10$ vertices, all of which are degree $3$: I am trying to show it is either planar or nonplanar, so I use the circle-chord method to create a circuit $abcdefghija$ (easy since ...
14 views

Complete bipartite graph from 2 to m points

How can I show that $K_{2,m}$ is planar for all m? I can't even seem to draw $K_{2,2}$ without intersection and if I draw it as a square then it seems to fail to be bipartite as the second set lies ...
15 views

88 views

Partitioning the edges of $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs

Why is it impossible to partition the edges in $K_n$ into $\lfloor \frac n6 \rfloor$ planar subgraphs for $n \ge 6$? I'm just stuck at the beginning and can't figure out how to go about this problem. ...
65 views

Counting edges in a finite connected graph where each vertex is exactly one of two values.

Let $p,q$ and $r$ be positive integers greater than $0$ with $q\neq r$. Suppose that $H$ is a finite connected graph without loops or multiedges on $p$ vertices with $q$ vertices of degree $r$, $r$ ...
32 views

Connected Planar Graph

In a connected planar graph, every vertex has degree $3$, and every face is bordered by $5$ or $6$ edges. How many faces are bordered by $5$ edges?
51 views

Extending Kuratowski's planarity theorem on finite graphs to countable infinite graphs.

As the title suggests. Kuratowski's theorem states that a graph is planar if and only if it does not contain a subdivision of $K_5$ or $K_3,_3$ I want to extend this result to "A infinite graph G ...
29 views

Hamiltonian cycle that contains a specified edge in a 3-connected cubic bipartite planar Hamiltonian graph

Assume that we have a 3-connected cubic bipartite planar graph with a Hamiltonian cycle. That graph must have at least 4 Hamiltonian cycles, because of Theorem 1 and Theorem 10 of this paper. I would ...