Question

ENG: When a graph with n vertices is isomorphically reduced to a plane, find the maximum value that can be edges if there is no part (surface) formed by 3 vertices. (Intersection points are not counted as three!) RU: Когда граф с n вершинами изоморфно сведен к плоскости, найдите максимальное значение, которое может быть ребрами, если нет части (поверхности), образованной 3 вершинами (точки пересечения не считаются за три!)

Answer 1

ответ:If a graph with n vertices is isomorphically reduced to a plane, and no part (surface) is formed by three vertices, this means that the graph is a planar graph.

In a planar graph, the maximum number of edges is given by the formula:

E ≤ 3V - 6

where E is the number of edges and V is the number of vertices.

Therefore, the maximum number of edges in a planar graph with n vertices is:

E ≤ 3n - 6

For example, in a planar graph with 6 vertices (n=6), the maximum number of edges would be 3 * 6 - 6 = 12 edges.

Пошаговое объяснение: