| If a graph G embeds on a particular surface then every minor of G also embeds on that same surface. | Если граф G вкладывается в определённую поверхность, то любой минор графа G также вложим в ту же поверхность. |
| Thus, by applying the polynomial time algorithm for testing whether a given graph contains any of the forbidden minors, it is possible to recognize the members of any minor-closed family in polynomial time. | Таким образом, при применении алгоритма с полиномиальным временем работы для проверки, содержит ли заданный граф какой-либо из запрещённых миноров, можно распознать члены любого минорно замкнутого семейства за полиномиальное время. |
| In the other direction, if the graph is not 2-vertex-connected, then it has an articulation vertex v separating some biconnected component of G from s and t. | В другом направлении, если граф не является вершинно 2-связным, то он имеет сочленяющую вершину v, отделяющую некоторую двусвязную компоненту графа G от s и t. |
| A classic result is Dirac's theorem, which states that every graph G with n vertices and minimum degree at least n/2 contains a Hamilton cycle. | Классическим результатом является теорема Дирака, которая утверждает, что любой граф G с n вершинами и минимальной степенью, не меньшей n/2, содержит гамильтонов цикл. |
| Wagner's theorem that a graph is planar if and only if it does not contain a minor (subgraph of a contraction) that is isomorphic to K5 or K3,3. | Теорема Вагнера, что граф планарен тогда и только тогда, когда он не содержит минора (подграфа стягиваний), который изоморфен K5 или K3,3. |
| In connection with these two results and several examples including the Chvátal graph, Branko Grünbaum conjectured in 1970 that for every k and l there exist k-chromatic k-regular graphs with girth l. | В связи с этими двумя результатами и несколькими примерами, включая граф Шватала, Бранко Грюнбаум высказал гипотезу в 1970 году, что для любых k и l существуют k-хроматические k-регулярные графы с обхватом l. |
| If the graph has maximum degree Δ, then the greedy approximation algorithm finds an O(log Δ)-approximation of a minimum dominating set. | Если граф имеет максимальную степень Δ, то жадный аппроксимационный алгоритм находит O(log Δ)-аппроксимацию минимального доминирующего множества. |
| The Desargue graph consists of the 20 edges of these two polygons together with an additional 10 edges connecting points of one decagon to the corresponding points of the other. | Граф Дезарга состоит из 20 рёбер этих двух многоугольников вместе с дополнительными 10 рёбрами, соединяющими точки одного десятиугольника с соответствующими точками другого. |
| The Robertson-Seymour theorem has an important consequence in computational complexity, due to the proof by Robertson and Seymour that, for each fixed graph G, there is a polynomial time algorithm for testing whether larger graphs have G as a minor. | Теорема Робертсона - Сеймура имеет важное следствие в теории вычислительной сложности, поскольку Робертсон и Сеймур доказали, что для каждого фиксированного графа G существует алгоритм полиномиального времени для проверки, имеет ли больший граф G в качестве минора. |
| Note that steps 1. and 2. result in an empty graph if H is planar, but the bounded number of vertices added in step 3. makes the statement consistent with Corollary 1. | Заметим, что шаги 1 и 2 дают пустые графы, если граф H планарен, но ограниченное число вершин, добавляемых на шаге 3, делает утверждение совместимым со Следствием 1. |
| Consider a graph G built from the triangulation T as follows: The vertices of G are the members of T plus the area outside the triangle. | Рассмотрим граф G, построенный по триангуляции T следующим образом: Вершинами G будут треугольники T и область за пределами большого треугольника. |
| This graph is not vertex-transitive: the automorphisms group has one orbit on vertices of size 8, and one of size 4. | Граф не является вершинно-транзитивным - группа автоморфизмов имеет только одну орбиту вершин длиной 8 и одну длиной 4. |
| For the same reason, the problem of testing whether a graph of bounded book thickness obeys a given formula of first order logic is fixed-parameter tractable. | По той же причине задача проверки, удовлетворяет ли граф с ограниченной книжной толщиной заданной формуле логики первого порядка, является разрешимой относительно фиксированного параметра. |
| The Schläfli graph has a total of 36 subgraphs of this form, one of which consists of the zero-one vectors in the eight-dimensional representation described above. | Граф Шлефли содержит 36 подграфов такого вида, один из которых состоит из векторов с координатами 0 и 1 в восьмимерном пространстве, как было описано выше. |
| An orientation of G is an assignment of a direction to each edge of G, making it into a directed graph. | Ориентация графа G - это назначение направления каждому ребру графа G, что превращает его в ориентированный граф. |
| Such graphs are called semi-symmetric graphs and were first studied by Folkman in 1967 who discovered the graph on 20 vertices that now is named after him. | Такие графы называются полусимметричными, их первым изучал Фолкман в 1967 и обнаружил граф с 20 вершинами, который был позже назван его именем. |
| The conjecture states that, among all graphs requiring n colors, the complete graph Kn is the one with the smallest crossing number. | Гипотеза утверждает, что среди всех графов, требующих n цветов, полный граф Kn находится среди графов, имеющих наименьшее число пересечений. |
| The graph of a finite distributive lattice has an edge between vertices a and b whenever I(a, b) = {a, b}. | Граф конечной дистрибутивной решётки имеет ребро между вершинами а и Ь, когда I(a, b) = {a, b}. |
| This group has two orbits of size 3 and one of size 6 on vertices, and thus this graph is not vertex-transitive. | Эта группа содержит две орбиты размера З и одну размера 6 на вершинах, а потому этот граф не вершинно транзитивен. |
| Note that the resulting graph has a linear number of edges because a WSPD has a linear number of pairs. | Заметим, что получающийся граф имеет линейное число рёбер, поскольку WSPD имеет линейное число пар. |
| Infinite skew polyhedron Projective polyhedron Spherical polyhedron Toroidal graph Whiteley (1979); Stewart (1980), pp. 15. | Бесконечный косой многогранник Проективный многогранник Сферический многогранник Тороидальный граф Whiteley (1979); Stewart (1980), стр. 15. |
| There is a simple algorithm for testing whether a graph is non-empty: loop through all of the pairs of vertices, testing whether each pair is connected by an edge. | Существует простой алгоритм тестирования, является ли граф не пустым - цикл через все пары вершин и проверка, связана ли каждая пара ребром. |
| Mohar (2005) conjectures that the minimum genus of a surface into which a Paley graph can be embedded is near this bound in the case that q is a square, and questions whether such a bound might hold more generally. | Мохар (Bojan Mohar, 2005) высказал гипотезу, что минимальный род поверхности, в которую может быть вложен граф Пэли, где-то около этого значения в случае, если q является квадратом, и поставил вопрос, можно ли обобщить такие границы. |
| If a graph G is not planar, but can be embedded on a surface of genus g, then it has a separator with O((gn)1/2) vertices. | Если граф G не планарен, но может быть вложен в поверхность рода g, то он имеет сепаратор с O((gn)1/2) вершинами. |
| The critical probability p is defined as the unique p such that a random graph G(n, p) possesses this property with probability equal to 1/2. | Критическая вероятность р определяется как единственное р, такое что случайный граф G(n, p) обладает этим свойством с вероятностью 1/2. |