0
$\begingroup$

By planar I mean there is no $K_{3,3}$ minor of $K_5$ minor. Also, I am only considering the $\mathbb{R}^2$ surface, not a torus not any other surfaces.

I know that to construct such graph, For $k \le 6$, it can be done easily by tesselation of regular $k$-gon and/or dual operation of graph. However, this construction does not work for $k \ge 7$ as regular $k$-gon cannot be "tightly packed together" (a little ambiguous here, I don't know how to explain what I am thinking, sorry about that) in $\mathbb{R}^2$.

Can anyone give me an idea on how to construct such infinite $k$-connected graph. A friend of mine gave me an idea of building a tree rooted at $v$ and extend it indefinitely such that some list of properties hold (I cannot remember all of them as there are several, but basically properties such as every vertex has to have degree at least $k$, etc)

P/S: I talked to my professor about this, and was told by the professor that any $k \ge 6$ has to be an infinite graph. But is there an example of 4-connected planar graph and 5-connected planar graph that is finite?

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
4
$\begingroup$

For a finite $5$-connected graph (also $4$-connected), use the graph of the icosahedron. For an infinite $k$-connected graph, just use the $(3,k)$ tiling of the hyperbolic plane, by triangles with angles $2\pi/k$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Okay.... I'm not sure if this is how it goes, but I'm going to give it a try. Say if we can find such tiling on the hyperbolic plane, how does one transform this into $\mathbb{R}^2$? The only technique I can think of is via stereographic projection, but I am not sure if that will work. $\endgroup$
    – user81529
    Commented Oct 24, 2015 at 20:23
  • $\begingroup$ @GuoXianYau: there is no topological difference between the Euclidean and the hyperbolic plane. $\endgroup$
    – Benoît Kloeckner
    Commented Oct 24, 2015 at 20:43
  • $\begingroup$ @BenoîtKloeckner I see. Thanks, I don't have much experience in geometry. $\endgroup$
    – user81529
    Commented Oct 24, 2015 at 20:47
1
$\begingroup$

Your friend has the right idea. You want to build a tree-like graph with rings running round each level so that after deleting any $k-1$ points you can still join any other two points "through infinity". More precisely, begin with a $k$-branching tree rooted at the origin, then add cycles through all vertices at equal distance from the root; observe that this graph can be drawn in the plane. After deleting any $k-1$ vertices, every remaining vertex still has at least one outward neighbour, so every vertex is connected to some sufficiently far out cycle.

The reason these graphs must be infinite for $k \geq 6$ is that every finite planar graph has a vertex of degree at most 5 by Euler's formula.

Improve this answer
$\endgroup$

You must log in to answer this question.