| In extremal graph theory, Apollonian networks are also exactly the n-vertex planar graphs in which the number of blocks achieves its maximum, n - 3, and the planar graphs in which the number of triangles achieves its maximum, 3n - 8. | В экстремальной теории графов графы Аполлония - это в точности планарные графы с n вершинами, в которых число блоков достигает максимального значения n - 3, и планарные графы, в которых число треугольником максимально и равно 3n - 8. |
| The gem shown is chordal but not distance-hereditary: in the subgraph induced by uvwx, the distance from u to x is 3, greater than the distance between the same vertices in the whole graph. | Граф-изумруд является хордальным, но не дистанционно-наследуемым - в подграфе, порождённом uvwx, расстояние от u до x равно 3, что больше, чем расстояние между теми же вершинами в полном графе. |
| There exist n-vertex planar graphs (for arbitrarily large values of n) such that, for every separator S that partitions the remaining graph into subgraphs of at most 2n/3 vertices, S has at least (4π3)n vertices, approximately 1.56n. | Существуют планарные графы с n вершинами (для произвольно больших значений n), такие, что для любого сепаратора S, разбивающего оставшийся граф на подграфы с не более чем 2n/3 вершинами, S имеет по меньшей мере (4π3)n вершин, примерно 1.56n. |
| The distance between two objects of an incidence structure - two points, two lines or a point and a line - can be defined to be the distance between the corresponding vertices in the incidence graph of the incidence structure. | Расстояние между двумя объектами структуры инцидентности - двумя точками, двумя прямыми или точкой и прямой - может быть определено как расстояние между двумя соответствующими вершинами в графе инцидентности структуры инцидентности. |
| If an n-vertex graph has thickness t then it necessarily has at most t(3n - 6) edges, from which it follows that its degeneracy is at most 6t - 1. | Если граф с n вершинами имеет толщину t, то число его рёбер не превосходит t(3n - 6), откуда следует, что вырожденность не превосходит 6t - 1. |
| The proof of subgraph isomorphism being NP-complete is simple and based on reduction of the clique problem, an NP-complete decision problem in which the input is a single graph G and a number k, and the question is whether G contains a complete subgraph with k vertices. | Доказательство NP-полноты задачи поиска изоморфного подграфа просто и основывается на сведении к этой задаче задачи о клике, NP-полной задачи разрешимости, в которой входом служит один граф G и число k, а вопрос состоит в следующем: содержит ли граф G полный подграф с k вершинами. |
| What is the maximum possible number of edges in an undirected graph G with n vertices which does not contain K3 (three vertices A, B, C with edges AB, AC, BC; i.e. a triangle) as a subgraph? | Каково максимально возможное число рёбер в неориентированном графе G с n вершинами, не содержащем K3 (три вершины A, B, C с рёбрами AB, AC, BC, то есть треугольник) в качестве подграфа? |
| In the mathematical field of graph theory, the Harries-Wong graph is a 3-regular undirected graph with 70 vertices and 105 edges. | В теории графов граф Харриса - Вонга - это З-регулярный неориентированный граф с 70 вершинами и 105 рёбрами. |
| The smallest 1-crossing cubic graph is the complete bipartite graph K3,3, with 6 vertices. | Наименьшие кубические графы с числом пересечений 1 - полный двудольный граф K3,3 с 6 вершинами. |
| If a connected graph with three or more vertices has maximum degree three, then its cutwidth equals the vertex separation number of its line graph. | Если связный граф с тремя или более вершинами имеет максимальную стпепень З, его ширина разреза равна величине вершинного разделения его рёберного графа. |
| The 6-vertex crown graph forms a cycle, and the 8-vertex crown graph is isomorphic to the graph of a cube. | Корона с шестью вершинами образует цикл, а корона с восемью вершинами изоморфна графу куба. |
| In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path (also called a graph geodesic) connecting them. | В теории графов расстоянием между двумя вершинами графа называется число рёбер в кратчайшем пути (также называемым геодезической графа). |
| The intersection graph of the twelve lines of the double six configuration is a twelve-vertex crown graph, a bipartite graph in which each vertex is adjacent to five out of the six vertices of the opposite color. | Граф пересечений двенадцати прямых конфигураций двойной шестёрки - это корона с 12 вершинами, двудольный граф, в котором каждая вершина смежна с пятью из шести вершин другого цвета. |
| In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or n-fan) Fn is a planar undirected graph with 2n+1 vertices and 3n edges. | Граф дружеских отношений (или граф датской мельницы, или n-лопастной вентилятор) Fn - это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами. |
| In the mathematical field of graph theory, the Robertson-Wegner graph is a 5-regular undirected graph with 30 vertices and 75 edges named after Neil Robertson and G. Wegner. | Граф Робертсона - Вегнера - это 5-регулярныйй неориентированный граф с 30 вершинами и 75 рёбрами, названный именами Нейла Робертсона и Дж. |
| The 46-vertex Tutte graph, and the smaller cubic non-Hamiltonian polyhedral graphs derived from it, have cyclic edge connectivity three. | Граф Татта с 46 вершинами и меньшие кубические негамильтоновы полиэдральные графы, полученные из него, имеют циклическую рёберную связность три. |
| The 5-vertex cycle graph has a neighborhood partial order of width five, so four is the maximum width that ensures perfect orderability. | Граф-цикл с 5 вершинами имеет ширину частичного порядка окрестностей, равную пяти, так что число четыре является максимальной шириной, обеспечивающей совершенное упорядочение. |
| The 2n-vertex crown graph may be embedded into four-dimensional Euclidean space in such a way that all of its edges have unit length. | Корону с 2n вершинами можно вложить в четырёхмерное евклидово пространство так, что все её рёбра будут иметь длину единица. |
| Any ten-vertex Hamiltonian 3-regular graph consists of a ten-vertex cycle C plus five chords. | Любой гамильтонов З-регулярный граф с десятью вершинами состоит из цикла с десятью вершинами цикла С, плюс пять хорд. |
| For k = 2, the unique forbidden minor is the 4-vertex complete graph K4. | Для к = 2 единственным запрещённым минором является полный граф K 4 с 4 вершинами. |
| In this case, the result of applying the Hajós construction is the Moser spindle, a seven-vertex unit distance graph that requires four colors. | В этом случае результатом применения построения Хайоша будет веретено Мозера, граф единичных расстояний с семью вершинами, требующий для раскраски четыре цвета. |
| Nešetřil & Thomas (1985) observed that Sachs' question about the chromatic number would be resolved by a proof of Hadwiger's conjecture that any k-chromatic graph has as a minor a k-vertex complete graph. | В 1985 году показано, что вопрос Сакса о хроматическом числе был бы решён, если была бы доказана гипотеза Хадвигера, что любой k {\displaystyle k} -хроматический граф имеет в качестве минора полный граф с k {\displaystyle k} вершинами. |
| 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 вершинами. |
| That is, if an n-vertex graph G is p-degenerate, then a monochromatic copy of G should exist in every two-edge-colored complete graph on cp n vertices. | Таким образом, если граф G с n вершинами является p-вырожденным, то монохроматическая копия графа G должна существовать в любом окрашенном двумя цветами графе с cp n вершинами. |
| 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 вершинами. |