| Sumner's proof shows, more strongly, that in any connected claw-free graph one can find a pair of adjacent vertices the removal of which leaves the remaining graph connected. | Доказательство Самнера показывает, строго говоря, что в любом связном графе без клешней можно найти пару сопряжённых вершин, удаление которых оставляет граф связным. |
| In this case, the graph G is a conflict graph: an edge in G between the nodes u and v denotes that u and v cannot be active simultaneously. | В этом случае граф G является графом конфликтов - ребро в G между вершинами u и v означает невозможность выполнения u и v одновременно. |
| For instance, the cubical graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. | Например, Q3 - это граф, образованный 8 вершинами и 12 рёбрами трёхмерного куба. |
| The Dürer graph is a well-covered graph, meaning that all of its maximal independent sets have the same number of vertices, four. | Граф Дюрера является хорошо укрытым, что означает, что все его наибольшие независимые множества имеют одно и то же число вершин - четыре. |
| They are strongly regular, with the same parameters and spectra as the line graph L(K8) of the complete graph K8. | Все они сильно регулярны и имеют те же параметры и спектр, что и рёберный граф L(K8) полного графа K8. |
| Turán also found the (unique) largest graph not containing Kk which is named after him, namely the Turán graph. | Туран также нашёл (уникальный) самый большой граф, не содержащий Кк, который назван его именем, а именно граф Турана. |
| The six neighbors of each vertex in the Paley graph of order 13 are connected in a cycle; that is, the graph is locally cyclic. | Шесть соседей каждой вершины в графе Пэли 13-го порядка соединены в цикл, так что граф локально цикличен. |
| The Ljubljana graph is the Levi graph of the Ljubljana configuration, a quadrangle-free configuration with 56 lines and 56 points. | Граф Любляны является графом Леви конфигурации Любляны, конфигурации без четырёхугольников с 56 прямыми и 56 точками. |
| The case of z(4; 3) is relatively simple: a 13-edge bipartite graph with four vertices on each side of the bipartition, and no K3,3 subgraph, may be obtained by adding one of the long diagonals to the graph of a cube. | Случай z(4; 3) относительно прост - двудольный граф с 13 рёбрами и четырьмя вершинами в каждой доле, не содержащий K3,3 подграфа, может быть получен путём добавления длинной диагонали к графу куба. |
| The Pappus graph is the Levi graph of the Pappus configuration, composed of 9 points and 9 lines. | Граф Паппа является графом Леви конфигурации Паппа, состоящей из 9 точек и 9 прямых. |
| In mathematics, a quiver is a directed graph. | В математике колчан - это ориентированный граф. |
| They said that the graph is dangerous. | Они сказали, что граф опасен. |
| The smallest graphs that are regular but not strongly regular are the cycle graph and the circulant graph on 6 vertices. | Наименьшие графы, которые регулярны, но не сильно регулярны - циклический граф и циркулянтный граф на шести вершинах. |
| That is, whenever a graph is both planar and 3-vertex-connected, there exists a polyhedron whose vertices and edges form an isomorphic graph. | Таким образом, если граф и планарен, и вершинно З-связен, существует многогранник, вершины и рёбра которого образуют изоморфный исходному граф. |
| The concept of thickness originates in the 1962 conjecture of Frank Harary: For any graph on 9 points, either itself or its complementary graph is non-planar. | Концепция толщины возникла в гипотезе Фрэнка Харари 1962 года: любой граф с 9 вершинами либо сам, либо его дополнение, является непланарным. |
| The vertex-connectivity, or just connectivity, of a graph is the largest k for which the graph is k-vertex-connected. | Вершинная связность, или просто связность, графа - это наибольшее к, для которого граф к-вершинно-связен. |
| That is, a graph is a line graph if and only if no subset of its vertices induces one of these nine graphs. | Таким образом, граф является рёберным тогда и только тогда, когда никакое подмножество вершин не порождает один из этих девяти. |
| The Grötzsch graph is an example of a 4-chromatic graph without a triangle, and the example can be generalised to the Mycielskians. | Граф Грёча - это пример 4-раскрашиваемого графа без треугольников, и этот пример может быть обобщен на граф Мычельского. |
| The vertex set (of an undirected graph) and the distance function form a metric space, if and only if the graph is connected. | Множество вершин (неориентированного графа) и функция расстояния образуют метрическое пространство в том и только в том случае, когда граф связен. |
| As a semi-symmetric graph, the Folkman graph is bipartite, and its automorphism group acts transitively on each of the two vertex sets of the bipartition. | Как полусимметричный граф, граф Фолкмана является двудольным и его группа автоморфизмов действует транзитивно на каждую долю вершин двудольного графа. |
| Every connected graph in which the domination number is half the number of vertices arises in this way, with the exception of the four-vertex cycle graph. | Любой связный граф, в котором число доминирования равно половине вершин, получается таким образом, за исключением цикла с четырьмя вершинами. |
| A graph is strongly chordal if and only if each of its induced subgraphs is a dually chordal graph. | Граф является строго хордальным тогда и только тогда, когда любой из его порождённых подграфов является двойственно-хордальным графом. |
| Because the problem of testing whether a graph is class 1 is NP-complete, there is no known polynomial time algorithm for edge-coloring every graph with an optimal number of colors. | Поскольку задача проверки, имеет ли граф класс 1, является NP-полной, не известно полиномиального по времени алгоритма рёберной раскраски для любого графа, дающего оптимальную раскраску. |
| It is also NP-hard to find an optimal coloring of the graph, because (via line graphs) this problem generalizes the NP-hard problem of computing the chromatic index of a graph. | Задача нахождения оптимальной раскраски такого графа тоже NP-трудна, поскольку (через рёберный граф) эта задача обобщает NP-трудную задачу вычисления хроматического числа графа. |
| Mycielski (1955) defined a construction, now called the Mycielskian, for forming a new triangle-free graph from another triangle-free graph. | Мычельский (Mycielski 1955) определил конструкцию, теперь называемую мычельскианом, которая образует новый граф без треугольников из другого графа без треугольников. |