Planar Graphs

Is it true that the resulting face is bounded by a non-self-intersecting cycle?

Is it true that if one more vertex is removed, then all faces will again be bounded by non-self-intersecting cycles?

Suppose that in the resulting graph every vertex has degree at least 3. Is it true that any vertex of the new graph can be deleted so as to obtain a graph all of whose faces are bounded by non-self-intersecting cycles?

Euler's formula. For any connected plane graph with $f$ faces, the equality $n - e + f = 2$ holds.

(For a proof see, e.g., [R]. From now on this result may be used without proof. This formula is often written in the form $V - E + F = 2$.)

Find an analogue of Euler's formula for a plane graph with $k$ connected components.

Neither of the graphs $K_{5}$ and $K_{3,3}$ can be drawn in the plane without self-intersections.

Fig. 5. Nonplanar graphs

In the plane, $n$ points are marked. It is allowed to join some two of them by a polygonal line not passing through the other points. Two players take turns joining some two not yet joined points by a polygonal line. It is required that these polygonal lines do not self-intersect and do not intersect anywhere except at the marked points. The player who cannot make a move loses. For which $n$ does the player who moves first win with correct play?

List all connected plane graphs (up to isomorphism) in which the degrees of all vertices are equal and the ``degrees'' of all faces are equal (i.e., the boundary of each face consists of the same number of edges).

Remark. If parts (1), (2), or (3) do not work out, solve the following parts. For the definition of isomorphism see Sec. 2.3.

There are exactly 5 convex regular polyhedra (all faces are regular polygons with the same number of sides, and the degrees of all vertices are equal) (up to isomorphism of their graphs). A construction of the corresponding polyhedra must be given; it is not assumed to be known.

For any connected plane graph without loops and multiple edges having more than two vertices, $2e \geq 3f$ and $e \leq 3n - 6$.

Every plane graph has a vertex of degree at most 5.

If every vertex of a connected plane graph has degree $d$ and the boundary of every face consists of exactly $k \geq 3$ edges, then

6 colors;

5 colors;

[You won't be able to prove it anyway.]

for recognizing whether a graph is planar (here you may use Kuratowski's theorem without proof);

for drawing a graph that is known to be planar in the plane without self-intersections.

Fáry's theorem. A plane graph can be drawn in the plane without self-intersections so that all edges are line segments.

A non-convex polygon with opaque sides is given. Call a vertex $A$ visible from a point $X$ if the interior of the segment $AX$ does not intersect the boundary of the polygon. Call the kernel of the polygon the set of its interior points from which all vertices of the polygon are visible. Prove that if a point of the kernel is joined by segments to several arbitrarily chosen vertices of the original polygon (at least two, and not necessarily all of them), then the polygon splits into polygons with nonempty kernels.

$K_{5}$;

$K_{3,3}$;

$K_{6}$;

$K_{3,4}$;

$K_{7}$;

$K_{4,4}$.

$K_{5}$;

$K_{3,3}$;

$K_{6}$;

$K_{3,4}$.

with 5 colors;

with 6 colors;

with 7 colors?