| It is the smallest bridgeless cubic graph with no Hamiltonian cycle. | Граф является наименьшим кубическим графом без моста, не имеющим гамильтонова цикла. |
| The 46-vertex Tutte graph, and the smaller cubic non-Hamiltonian polyhedral graphs derived from it, have cyclic edge connectivity three. | Граф Татта с 46 вершинами и меньшие кубические негамильтоновы полиэдральные графы, полученные из него, имеют циклическую рёберную связность три. |
| In the following figure, the graph C is a double cover of the graph H: The graph C is a covering graph of H: there is a surjective local isomorphism f from C to H, the one indicated by the colours. | На рисунке граф С является двойным покрытием графа Н: Граф С является покрывающим графом графа Н - существует сюръективный локальный изоморфизм f из C в H, показанный на рисунке цветами. |
| They say that a graph family F is somewhere dense if there exists a finite value of d for which the d-shallow minors of graphs in F consist of every finite graph. | Они говорят, что граф семейство графов F кое-где плотно, если существует конечное значение d, для которого множество миноров глубины d графов из F содержит любой конечный граф. |
| This was seen by Jon Folkman, whose paper, published in 1967, includes the smallest semi-symmetric graph, now known as the Folkman graph, on 20 vertices. | Статью увидел Джон Фолкман, статья которого, опубликованная в 1967, включала наименьший полусимметричный граф, известный ныне как Граф Фолкмана, с 20 вершинами. |
| Takeo (1960) claimed erroneously that all Apollonian networks have Hamiltonian cycles; however, the Goldner-Harary graph provides a counterexample. | Такео ошибочно утверждал, что все графы Аполлония имеют гамильтоновы циклы, однако граф Голднера-Харари служит контрпримером. |
| In graph theory, a clique graph of an undirected graph G is another graph K(G) that represents the structure of cliques in G. Clique graphs were discussed at least as early as 1968, and a characterization of clique graphs was given in 1971. | Кликовый граф неориентированного графа G - это другой граф K(G), который представляет структуру клик графа G. Кликовые графы обсуждались по меньшей мере с 1968-го года, а описание кликовых графов было дано в 1971-м году. |
| In particular the Grötzsch graph, an 11-vertex graph formed by repeated application of Mycielski's construction, is a triangle-free graph that cannot be colored with fewer than four colors, and is the smallest graph with this property. | В частности, граф Грёча, граф с 11 вершинами, образованный повторением конструкции Мычельского, является графом без треугольников, который нельзя раскрасить меньше чем четырьмя цветами, и является наименьшим графом с этими свойствами. |
| It is possible to test whether a given graph is an indifference graph in linear time, by using PQ trees to construct an interval representation of the graph and then testing whether a vertex ordering derived from this representation satisfies the properties of an indifference graph. | Можно проверить, является ли данный граф индифферентным за линейное время с помощью PQ-деревьев для построения интервальных представлений графа и затем проверки, удовлетворяет ли упорядочение вершин, производное от этого представления, свойствам индифферентного графа. |
| In a biconnected graph of circuit rank less than three (such as a cycle graph or theta graph) every cycle is peripheral, but every biconnected graph with circuit rank three or more has a non-peripheral cycle, which may be found in linear time. | В двусвязном графе с контурным рангом, меньшим трёх, (таком как цикл или тета-граф), любой цикл является периферийным, но любой двусвязный граф с контурным рангом три и более имеет непериферийный цикл, который может быть найден за линейное время. |
| Roughly speaking, in order to solve the undirected s-t connectivity problem in logarithmic space, the input graph is transformed, using a combination of powering and the zigzag product, into a constant-degree regular graph with a logarithmic diameter. | Грубо говоря, для решения ненаправленной задачи s-t связности в логарифмическом пространстве памяти исходный граф преобразуется с использованием комбинации произведения и зигзаг-произведения в регулярный граф постоянной степени с логарифмическим диаметром. |
| The three smallest cubic semi-symmetric graphs are the Gray graph, with 54 vertices, this the smallest of the Iofina-Ivanov graphs with 110, and the Ljubljana graph with 112. | Три наименьших кубических полусимметричных графа - это граф Грея с 54 вершинами, этот наименьший из графов Иванова - Иофиновой с 110 вершинами и граф Любляны с 112 вершинами. |
| A Markov chain in which all states are recurrent has a strongly connected state transition graph, and the Markov chain is aperiodic if and only if this graph is aperiodic. | Цепь Маркова, в которой все состояния рекуррентны, имеет сильно связный граф переходов и цепь Маркова апериодична тогда и только тогда, когда этот граф апериодичен. |
| Just as no graph with a loop edge has a proper coloring, no graph with a bridge can have a nowhere-zero flow (in any group). | Поскольку никакой граф с петлёй не имеет правильной раскраски, никакой граф, имеющий мосты, не может иметь нигде не нулевой поток (в любой группе). |
| A strongly regular graph is a regular graph in which every two adjacent vertices have the same number of shared neighbours and every two non-adjacent vertices have the same number of shared neighbours. | Сильно регулярный граф есть регулярный граф, у которого каждая пара смежных вершин имеет одинаковое количество l общих соседей, и каждая пара несмежных вершин имеет одинаковое количество n общих соседей. |
| It states that, if one forms an undirected graph from the vertices and edges of a convex d-dimensional polyhedron or polytope (its skeleton), then the resulting graph is at least d-vertex-connected: the removal of any d - 1 vertices leaves a connected subgraph. | Теорема утверждает, что если образовать неориентированный граф из вершин и рёбер выпуклого d-мерного многогранника (его скелет), то полученный граф по меньшей мере вершинно d-связен - удаление любого набора из d - 1 вершин оставляет связный подграф. |
| For instance there are three nonisomorphic 10-cages, each with 70 vertices: the Balaban 10-cage, the Harries graph and the Harries-Wong graph. | Например, существует три неизоморфных 10-клетки, каждая с 70 вершинами - 10-клетка Балабана, граф Харриса и граф Харриса - Вонга. |
| Levi graphs of configurations are biregular, and every biregular graph with girth at least six can be viewed as the Levi graph of an abstract configuration. | Графы Леви конфигураций являются бирегулярными (англ.)русск. и любой бирегулярнй граф с обхватом как минимум шесть можно рассматривать как граф Леви абстрактной конфигурации. |
| A graph G is said to be k-constructible (or Hajós-k-constructible) when it formed in one of the following three ways: The complete graph Kk is k-constructible. | Говорят, что граф G k-конструируемый (или k-конструируемый по Хайошу), если он образован одним из трёх способов: Полный граф Kk является k-конструируемым. |
| Spinrad (1994) gives an O(n2)-time algorithm that tests whether a given n-vertex undirected graph is a circle graph and, if it is, constructs a set of chords that represents it. | Спинрад представил алгоритм, работающий за время O(n2), который проверяет, является ли заданный неориентированный граф с n вершинами круговым, и если он круговой, строит множество хорд, которые дают круговой граф. |
| They proved that it was the unique 112-vertices edge- but not vertex-transitive cubic graph and therefore that was the graph found by Foster. | Они доказали, что граф был единственным 112-вершинным рёберно транзитивным, но не вершинно транзитивным, кубическим графом, а потому это тот самый граф, который нашёл Фостер. |
| Their algorithm partitions the graph into triconnected components, after which there is a unique planar embedding (up to the choice of the outer face) and the cycles in a 2-basis can be assumed to be all the peripheral cycles of the graph. | Их алгоритм разбивает граф на трисвязные компоненты, после чего имеется единственное планарное вложение (с точностью до выбора внешней грани) и циклы в 2-базисе будут всеми периферийными циклами графа. |
| In a 1-planar embedding of an optimal 1-planar graph, the uncrossed edges necessarily form a quadrangulation (a polyhedral graph in which every face is a quadrilateral). | В 1-планарном вложении оптимального 1-планарного графа непересекающиеся рёбра обязательно образуют разбиение на четырёхугольники (т.е. образуют полиэдральный граф, в котором каждая грань является четырёхугольником). |
| Conversely, if a graph has a cycle, then every chordal completion of the graph includes at least one triangle consisting of three consecutive vertices of the triangle, from which it follows that its treewidth is at least two. | Обратно, если граф имеет цикл, то любое хордальное дополнение графа содержит по меньшей мере один треугольник, откуда следует, что древесная ширина графа не меньше двух. |
| Kawarabayashi, Kreutzer & Mohar (2010) described a linear time algorithm that tests whether a graph is linklessly embeddable and, if so, constructs a flat embedding of the graph. | Каравабайши, Крейцер и Мохар описали алгоритм с линейным временем работы, проверяющий, вложим ли граф незацепленно, и, если вложим, строит плоское вложение графа. |