| Whenever there is more than one triangle, the dual graph (like any tree) must have a vertex with only one neighbor, corresponding to a triangle that is adjacent to other triangles along only one of its sides. | Если в триангуляции существует более одного треугольника, двойственный граф (как и всякое дерево) должен иметь вершину, у которой всего один сосед, что соответствует треугольнику, смежному лишь одному другому треугольнику. |
| Any of the graphs in the Petersen family can be transformed into any other graph in the family by Δ-Y or Y-Δ transforms, operations in which a triangle is replaced by a degree-three vertex or vice versa. | Любой из графов семейства Петерсена может быть преобразован в любой другой граф семейства Δ-Y или Y-Δ преобразованиями, операциями, при которых треугольник заменяется вершиной степени 3, или наоборот. |
| A complete bipartite graph Ka, b has a RAC drawing with straight edges if and only if either min(a, b) <= 2 or a + b <= 7. | Полный двудольный граф Ка, Ь имеет РПУ рисунок с рёбрами в виде отрезков тогда и только тога, когда min(a, b) <= 2 или a + b <= 7. |
| A graph is known as graceful when its vertices are labeled from 0 to |V|, the size of the graph, and this labeling induces an edge labeling from 1 to |E|. | Граф называется грациозным, если его вершины размечены числами от 0 до |E|, размера графа, и эта разметка порождает рёберную разметку от 1 до |E|. |
| The order in which a sequence of such contractions and deletions is performed on G does not affect the resulting graph H. Graph minors are often studied in the more general context of matroid minors. | Порядок, в котором производится стягивания и удаления в G, не влияют на результирующий граф H. Миноры графов часто изучаются в более общем контексте миноров матроидов. |
| If X {\displaystyle X} is a graph with the combinatorial metric then it is a real tree if and only if it is a tree (i.e. it has no cycles). | Если Х {\displaystyle X} - это граф с комбинаторной метрикой, тогда это метрическое дерево, тогда и только тогда, когда граф X {\displaystyle X} - дерево (т. е. не имеет циклов). |
| The fact that this number is at least this large follows from the fact that the graph has 10 vertices, at most three of which can be in any independent set. | Факт, что это число не меньше указанного значения, следует из того, что граф имеет 10 вершин и максимум три из них могут быть в каком-либо независимом множестве. |
| Conversely, every directed acyclic graph that has a bimodal planar embedding with a consistent assignment has an upward planar drawing, that can be constructed from it in linear time. | В обратную сторону, любой направленный ациклический граф, имеющий бимодальное планарное вложение с правильным назначением имеет восходящее планарное представление, которое может быть построено за линейное время. |
| Specifically, by truncating a separator hierarchy at an appropriate level, one may find a separator of size O(n/log n) the removal of which partitions the graph into subgraphs of size c log n, for any constant c. | В частности, путём усечения иерархии сепараторов в подходящем месте можно найти сепаратор размера O(n/log n), удаление которого разбивает граф на подграфы размера c log n для любой константы c. |
| More strongly, if a Henson graph Gi is partitioned into any finite number of induced subgraphs, then at least one of these subgraphs includes all i-clique-free finite graphs as induced subgraphs. | Более строго, если граф Хэнсона Gi разбить на любое конечное число порождённых подграфов, то по меньшей мере один из этих графов включает все свободные от i-клик конечные графы в качестве порождённых подграфов. |
| On the other hand, the property of being empty is non-trivial, because the empty graph possesses this property, but non-empty graphs do not. | Но с другой стороны, свойство быть пустым нетривиально, поскольку пустой граф обладает данным свойством, а непустой не обладает. |
| For instance, the graph in the illustration may be partitioned in this way into a cycle of five edges and a path of three edges. | Например, граф на иллюстрации может быть разбит этим образом на циклы с пятью рёбрами и пути с тремя рёбрами. |
| The fourth forbidden minor for treewidth three, the pentagonal prism, has the cube graph as a minor, so it is not minimal for branchwidth three. | Четвёртый запрещённый минор для древесной ширины три, граф пентагональной призмы, имеет граф куба в качестве минора, так что он не является минимальным для ширины ветвления три. |
| The satisfiability problem for a formula of monadic second-order logic is the problem of determining whether there exists at least one graph (possibly within a restricted family of graphs) for which the formula is true. | Проблема выполнимости для формул логики второго порядка является задачей определения, существует ли по меньшей мере один граф (возможно, принадлежащий ограниченному семейству графов), для которого формула верна. |
| The underlying graph of any antimatroid, having a vertex for each set in the antimatroid and an edge for every two sets that differ by a single element, is always a partial cube. | Лежащий в основе любого антиматроида граф, имеющий вершину для каждого множества в антиматроиде и ребро для любых двух множеств, отличающихся единственным элементом, всегда является частичным кубом. |
| If a graph does not have finite chromatic number, then the De Bruijn-Erdős theorem implies that it must contain finite subgraphs of every possible finite chromatic number. | Если граф не имеет конечного хроматического числа, тогда из теоремы де Брёйна - Эрдёша следует, что граф должен содержать конечные подграфы для каждого возможного хроматического числа. |
| If a graph G does not have a k-vertex separator, then every set X of at most k vertices has a (unique) X-flap with more than 2n/3 vertices. | Если граф G не имеет сепаратора с k вершинами, то любое множество X с максимум k вершинами имеет (уникальный) X-борт с более чем 2n/3 вершинами. |
| If a 3-regular graph is Hamiltonian, its edges can be colored with three colors: use alternating colors for the edges on the Hamiltonian cycle (which must have even length by the handshaking lemma) and a third color for all remaining edges. | Если З-однородный граф гамильтонов, его рёбра могут быть выкрашены в три цвета - используем поочерёдную раскраску рёбер двумя цветами вдоль гамильтонова цикла (который должен иметь чётную длину по лемме о рукопожатиях), а третьим цветом выкрашиваем все оставшиеся рёбра. |
| By manipulating the Euler characteristic, one can show that every graph embedded in the given surface must have at least one vertex of degree less than the given bound. | Манипулируя характеристикой Эйлера, можно показать, что любой граф, вложенный в данную поверхность, должен иметь по меньшей мере одну вершину со степенью, меньшей указанной граничной величины. |
| The first use of the phrase "perfect graph" appears to be in a 1963 paper of Claude Berge, after whom Berge graphs are named. | Первое применение термина «совершенный граф» появилось в 1963 году в статье Клауди Бержа, откуда и появилось название «графы Бержа». |
| The resulting graph is said to be obtained from G by adding a vortex of depth at most k (to the face F) provided that no vertex on the boundary of F appears in more than k of the intervals in Λ. | Говорят, что образованный граф получен из графа G добавлением вихря глубины, не превосходящей k (к грани F), если никакая вершина на границе F не появляется в более чем k интервалах из Λ. |
| Castagna & Prins (1972) attribute the proof of Hamiltonicity of a class of generalized Petersen graphs that includes the Dürer graph to a 1968 Ph.D. thesis of G. N. Robertson at the University of Waterloo. | Кастанья и Принс (Кастанья, Принс (1972)) приписывают доказательство гамильтоновости класса обобщённых графов Петерсона, в который входит граф Дюрера, тезисам диссертации 1968 года Робертсона (G. N. Robertson) из университета Ватерлоо. |
| In the other direction, the proof is more difficult, and involves showing that in each case (except the Klein bottle) a complete graph with a number of vertices equal to the given number of colors can be embedded on the surface. | В обратном направлении доказательство сложнее, в нём показывается, что во всех случаях (за исключением бутылки Клейна) полный граф с числом вершин, равным данному числу цветов, может быть вложен в поверхность. |
| Therefore, this graph can be embedded as a Whitney triangulation of a torus, in which every face is a triangle and every triangle is a face. | Таким образом, этот граф может быть вложен в триангуляцию Уитни тора, в которой каждая грань является треугольником и каждый треугольник является гранью. |
| However, Herschel's paper described solutions for the Icosian game only on the graphs of the regular tetrahedron and regular icosahedron; it did not describe the Herschel graph. | Однако статья Хершеля описывает решения для игры «Икосиан» только для тетраэдра и икосаэдра, и не описывает граф Хершеля. |