| A graph with exactly 3n/3 maximal independent sets is easy to construct: simply take the disjoint union of n/3 triangle graphs. | Граф, имеющий ровно 3n/3 наибольших независимых множеств, легко построить, просто взяв несвязный набор n/3 треугольных графов. |
| If the graph is not biconnected, its biconnected components may be colored separately and then the colorings combined. | Если граф не является двусвязным, его двусвязные компоненты можно раскрасить по отдельности, а затем объединить раскраски. |
| The model represents a system as directed graph, where vertices are either subjects or objects. | Модель представляет всю систему как направленный граф, где узлы - либо объекты, либо субъекты. |
| The complete bipartite graph Km, n has edge covering number max(m, n). | Полный двудольный граф Km, n имеет число рёберного покрытия max(m, n). |
| In these methods, the image is modeled as a weighted, undirected graph. | В этих методах изображение представляется как взвешенный неориентированный граф. |
| Every planar hypohamiltonian graph has at least one vertex with only three incident edges. | Любой планарный гипогамильтонов граф имеет по меньшей мере одну вершину только с тремя инцидентными рёбрами. |
| A cograph is a graph in which every connected induced subgraph has a disconnected complement. | Кограф - это граф, в котором любой связный порождённый подграф имеет несвязное дополнение. |
| A graph with arboricity a is (a, 0)-decomposable. | Граф с древесностью а является (а, 0)-разложимым. |
| It is not possible to use Grinberg's theorem to find counterexamples to Barnette's conjecture, that every cubic bipartite polyhedral graph is Hamiltonian. | Невозможно использовать теорему Гринберга для поиска контрпримеров гипотезе Барнетта, что любой кубический двудольный полиэдральный граф гамильтонов. |
| If a graph is 2-factorable, then it has to be 2k-regular for some integer k. | Если граф 2-факторизуем, то он должен быть 2k-регулярным для некоторого целого k. |
| Hall's marriage theorem can be used to show that a k-regular bipartite graph contains a perfect matching. | С помощью теоремы Холла о свадьбах можно показать, что к-правильный двудольный граф содержит совершенное сочетание. |
| Note that a moral graph is not necessarily chordal. | Заметим, что моральный граф не обязательно хордален. |
| The Heawood graph forms a subdivision of the torus with seven mutually adjacent regions, showing that this bound is tight. | Граф Хивуда образует разбиение тора на семь взаимно смежных областей, что показывает, что граница точна. |
| The case that n = 3 gives the well-known Petersen graph. | В случае, когда n = 3 {\displaystyle n=3} получаем хорошо известный граф Петерсена. |
| More were found later: first, the Errera graph in 1921, then the Kittell graph in 1935, with 23 vertices, and finally two minimal counter-examples (the Soifer graph in 1997 and the Fritsch graph in 1998, both of order 9). | Другие контрпримеры были найдены позже, это граф Эрреры в 1921, граф Киттелля в 1935 с 23 вершинами и, наконец, два минимальных контрпримера (граф Сойфера в 1997 и граф Фрича в 1998, оба порядка 9). |
| An alternative formulation is to use a graph in which each exit point is connected back to the entry point. | В другой формулировке используется граф, в котором каждая точка выхода соединена с точкой входа. |
| This property plays a key role in a proof that testing whether a graph can be covered by four perfect matchings is NP-complete. | Это свойство играет ключевую роль в доказательстве, что проверка, можно ли покрыть граф четырьмя паросочетаниями, является NP-полной задачей. |
| Every finite graph has a book embedding onto a book with a large enough number of pages. | Любой конечный граф имеет книжное вложение в книгу с достаточно большим числом страниц. |
| A well-covered graph is one in which every minimal cover is also minimum. | Хорошо покрытый граф - это граф, в котором любое минимальное покрытие является также наименьшим. |
| Every finite connected undirected graph has at least one Trémaux tree. | Любой конечный связный неориентированный граф имеет по меньшей мере одно дерево Тремо. |
| Not every infinite graph has a normal spanning tree. | Не любой бесконечный граф имеет нормальное остовное дерево. |
| Every graph has a cycle basis in which every cycle is an induced cycle. | Любой граф имеет базис циклов в котором каждый цикл является порождённым циклом. |
| A cograph is a graph all of whose connected induced subgraphs have diameter at most 2. | Кограф - это граф, у всех связных порождённых подграфов которого диаметр не превосходит 2. |
| In many discussions the directions of the edges are ignored and the NNG is defined as an ordinary (undirected) graph. | Во многих обсуждениях направление рёбер игнорируется и ГБС определяется как обычный (неориентированный) граф. |
| Except for the complete graphs, it is the only Kneser graph whose distinguishing number is not two. | За исключением полных графов, есть только кнезеровский граф, характерное число которого не равно двум. |