Editing Glossary of graph theory

{{Short description|none}}
{{wiktionary|Appendix:Glossary of graph theory}}
{{see also|Gallery of named graphs}}

This is a '''glossary of graph theory'''. [[Graph theory]] is the study of [[graph (discrete mathematics)|graphs]], systems of nodes or [[vertex (graph theory)|vertices]] connected in pairs by lines or [[#edge|edges]].

{{Compact ToC|short1|seealso=yes}}

==Symbols==
{{glossary}}

{{term|square bracket|Square brackets [ ]}}
{{defn|{{math|''G''[''S'']}} is the {{gli|induced|induced subgraph}} of a graph {{mvar|G}} for vertex subset {{mvar|S}}.}}

{{term|′|Prime symbol '}}
{{defn|The [[Prime (symbol)|prime symbol]] is often used to modify notation for graph invariants so that it applies to the [[line graph]] instead of the given graph. For instance, {{math|''&alpha;''(''G'')}} is the independence number of a graph; {{math|''&alpha;''′(''G'')}} is the matching number of the graph, which equals the independence number of its line graph. Similarly, {{math|''&chi;''(''G'')}} is the chromatic number of a graph; {{math|''&chi;''{{hsp}}′(''G'')}} is the chromatic index of the graph, which equals the chromatic number of its line graph.}}

{{glossary end}}

==A==
{{glossary}}

{{term|absorbing}}
{{defn|An absorbing set <math>A</math> of a directed graph <math>G</math> is a set of vertices such that for any vertex <math>v \in G \setminus A</math>, there is an edge from <math>v</math> towards a vertex of <math>A</math>.}}

{{term|achromatic}}
{{defn|The [[achromatic number]] of a graph is the maximum number of colors in a complete coloring.<ref>{{citation|last1=Farber|first1=M.|last2=Hahn|first2=G.|last3=Hell|first3=P.|author3-link=Pavol Hell|last4=Miller|first4=D. J.|title=Concerning the achromatic number of graphs|journal=Journal of Combinatorial Theory, Series B|volume=40|issue=1|year=1986|pages=21–39|doi=10.1016/0095-8956(86)90062-6|doi-access=free}}.</ref>}}

{{term|acyclic}}
{{defn|no=1|A graph is acyclic if it has no cycles. An undirected acyclic graph is the same thing as a [[Tree (graph theory)|forest]]. An acyclic directed graph, which is a digraph without directed cycles, is often called a [[directed acyclic graph]], especially in computer science.<ref name="clrs">{{citation|title=Introduction to Algorithms|year=2001|publisher=MIT Press and McGraw-Hill|first1=Thomas H.|last1=Cormen|author1-link=Thomas H. Cormen|first2=Charles E.|last2=Leiserson|author2-link=Charles E. Leiserson|first3=Ronald L.|last3=Rivest|author3-link=Ron Rivest|first4=Clifford|last4=Stein|author4-link=Clifford Stein|chapter=B.4 Graphs|pages=1080–1084|edition=2|title-link=Introduction to Algorithms}}.</ref>}}
{{defn|no=2|An [[acyclic coloring]] of an undirected graph is a proper coloring in which every two color classes induce a forest.<ref>{{Citation | doi = 10.1007/BF02764716 | doi-access=free | last1 = Grünbaum | first1 = B. | author-link = Branko Grünbaum | year = 1973 | title = Acyclic colorings of planar graphs | journal = [[Israel Journal of Mathematics]] | volume = 14 | issue = 4| pages = 390–408}}.</ref>}}

{{term|adjacency matrix}}
{{defn|The [[adjacency matrix]] of a graph is a matrix whose rows and columns are both indexed by vertices of the graph, with a one in the cell for row {{mvar|i}} and column {{mvar|j}} when vertices {{mvar|i}} and {{mvar|j}} are adjacent, and a zero otherwise.<ref>{{harvtxt|Cormen|Leiserson|Rivest|Stein|2001}}, p.&nbsp;529.</ref>}}

{{term|adjacent}}
{{defn|no=1|The relation between two vertices that are both endpoints of the same edge.<ref name="clrs"/>}}
{{defn|no=2|The relation between two distinct edges that share an end vertex.<ref name="diestel">{{citation|title=Graph Theory|year=2017|publisher=Springer-Verlag|location=Berlin, New York|first=Reinhard|last=Diestel|chapter=1.1 Graphs|series=Graduate Texts in Mathematics|volume=173|pages=3|edition=5th|doi=10.1007/978-3-662-53622-3|isbn=978-3-662-53621-6}}.</ref>}}

{{term|alpha|''&alpha;''}}
{{defn|For a graph {{mvar|G}}, {{math|''&alpha;''(''G'')}} (using the Greek letter alpha) is its independence number (see {{gli|independent}}), and {{math|''&alpha;''′(''G'')}} is its matching number (see {{gli|matching}}).}}

{{term|alternating}}
{{defn|In a graph with a matching, an alternating path is a path whose edges alternate between matched and unmatched edges. An alternating cycle is, similarly, a cycle whose edges alternate between matched and unmatched edges. An augmenting path is an alternating path that starts and ends at unsaturated vertices. A larger matching can be found as the [[symmetric difference]] of the matching and the augmenting path; a matching is maximum if and only if it has no augmenting path.}}

{{term|antichain}}
{{defn|In a [[directed acyclic graph]], a subset {{mvar|S}} of vertices that are pairwise incomparable, i.e., for any <math>x \leq y </math> in {{mvar|S}}, there is no directed path from {{mvar|x}} to {{mvar|y}} or from {{mvar|y}} to {{mvar|x}}. Inspired by the notion of [[antichain]]s in [[partially ordered set]]s.}}

{{term|anti-edge}}
{{defn|Synonym for ''non-edge'', a pair of non-adjacent vertices.}}

{{term|anti-triangle}}
{{defn|A three-vertex independent set, the complement of a triangle.}}

{{term|apex}}
{{defn|no=1|An [[apex graph]] is a graph in which one vertex can be removed, leaving a {{gli|planar}} subgraph. The removed vertex is called the apex. A {{mvar|k}}-apex graph is a graph that can be made planar by the removal of {{mvar|k}} vertices.}}
{{defn|no=2|Synonym for [[universal vertex]], a vertex adjacent to all other vertices.}}

{{term|arborescence}}
{{defn|Synonym for a rooted and directed tree; see {{gli|tree}}.}}

{{term|arc}}
{{defn|See {{gli|edge}}.}}

{{term|arrow}}
{{defn|An [[ordered pair]] of {{gli|vertex|vertices}}, such as an {{gli|edge}} in a {{gli|directed graph}}. An arrow {{math|(''x'', ''y'')}} has a {{gli|tail}} {{math|''x''}}, a {{gli|head}} {{math|''y''}}, and a {{gli|direction}} {{math|from ''x'' to ''y''}}; {{math|''y''}} is said to be the {{gli|direct successor}} to {{math|''x''}} and {{math|''x''}} the {{gli|direct predecessor}} to {{math|''y''}}. The arrow {{math|(''y'', ''x'')}} is the {{gli|inverted arrow}} of the arrow {{math|(''x'', ''y'')}}.}}

{{term|articulation point|[[articulation point]]}}
{{defn|A {{gli|vertex}} in a {{gli|connected graph}} whose removal would {{gli|disconnect}} the graph. More generally, a vertex whose removal increases the number of {{gli|component}}s.}}

{{term|k-ary|-ary}}
{{defn|A [[K-ary tree|{{mvar|k}}-ary tree]] is a rooted tree in which every internal vertex has no more than {{mvar|k}} children. A 1-ary tree is just a path. A 2-ary tree is also called a [[binary tree]], although that term more properly refers to 2-ary trees in which the children of each node are distinguished as being left or right children (with at most one of each type).  A {{mvar|k}}-ary tree is said to be complete if every internal vertex has exactly {{mvar|k}} children.}}

{{term|augmenting}}
{{defn|A special type of alternating path; see {{gli|alternating}}.}}

{{term|automorphism}}
{{defn|A [[graph automorphism]] is a symmetry of a graph, an isomorphism from the graph to itself.}}

{{glossary end}}

==B==
{{glossary}}

{{term|bag}}
{{defn|One of the sets of vertices in a {{gli|tree decomposition}}.}}

{{term|balanced}}
{{defn|A bipartite or multipartite graph is balanced if each two subsets of its vertex partition have sizes within one of each other.}}

{{term|ball}}
{{defn|A ball (also known as a neighborhood ball or distance ball) is the set of all vertices that are at most distance r from a vertex. More formally, for a given vertex v and radius r, the ball B(v,r) consists of all vertices whose shortest path distance to v is less than or equal to r.}}

{{term|bandwidth}}
{{defn|The [[Graph bandwidth|bandwidth]] of a graph {{mvar|G}} is the minimum, over all orderings of vertices of {{mvar|G}}, of the length of the longest edge (the number of steps in the ordering between its two endpoints). It is also one less than the size of the maximum clique in a proper interval completion of {{mvar|G}}, chosen to minimize the clique size.}}

{{term|biclique}}
{{defn|Synonym for [[complete bipartite graph]] or complete bipartite subgraph; see {{gli|complete}}.}}

{{term|biconnected}}
{{defn|Usually a synonym for [[k-vertex-connected graph|{{math|2}}-vertex-connected]], but sometimes includes ''K''<sub>2</sub> though it is not 2-connected. See {{gli|connected}}; for [[biconnected component]]s, see {{gli|component}}.}}

{{term|binding number}}
{{defn|The smallest possible ratio of the number of neighbors of a proper subset of vertices to the size of the subset.<ref>{{Citation | first = D. R. | last = Woodall | title = The Binding Number of a Graph and its Anderson Number | journal= J. Combin. Theory Ser. B| year = 1973 | volume = 15 | issue = 3 |pages=225–255 | doi=10.1016/0095-8956(73)90038-5| doi-access = free }}</ref>}}

{{term|bipartite}}
{{defn|A [[bipartite graph]] is a graph whose vertices can be divided into two disjoint sets such that the vertices in one set are not connected to each other, but may be connected to vertices in the other set. Put another way, a bipartite graph is a graph with no odd cycles; equivalently, it is a graph that may be properly colored with two colors. Bipartite graphs are often written {{math|1=''G'' = (''U'',''V'',''E'')}} where {{mvar|U}} and {{mvar|V}} are the subsets of vertices of each color. However, unless the graph is connected, it may not have a unique 2-coloring.}}

{{term|biregular}}
{{defn|A [[biregular graph]] is a {{gli|bipartite}} graph in which there are only two different vertex degrees, one for each set of the vertex bipartition.}}

{{term|block}}
{{defn|no=1|A block of a graph {{mvar|G}} is a maximal subgraph which is either an isolated vertex, a bridge edge, or a 2-connected subgraph. If a block is 2-connected, every pair of vertices in it belong to a common cycle. Every edge of a graph belongs in exactly one block.}}
{{defn|no=2|The block graph of a graph {{mvar|G}} is another graph whose vertices are the blocks of {{mvar|G}}, with an edge connecting two vertices when the corresponding blocks share an articulation point; that is, it is the intersection graph of the blocks of {{mvar|G}}.  The block graph of any graph is a {{gli|forest}}.}}
{{defn|no=3|The block-cut (or block-cutpoint) graph of a graph {{mvar|G}} is a bipartite graph where one partite set consists of the cut-vertices of {{mvar|G}}, and the other has a vertex <math>b_i</math> for each block <math>B_i</math> of {{mvar|G}}. When {{mvar|G}} is connected, its block-cutpoint graph is a tree.}}
{{defn|no=4|A [[block graph]] (also called a clique tree if connected, and sometimes erroneously called a Husimi tree) is a graph all of whose blocks are complete graphs. A {{gli|forest}} is a block graph; so in particular the block graph of any graph is a block graph, and every block graph may be constructed as the block graph of a graph.}}

{{term|bond}}
{{defn|A {{gli|minimal}} {{gli|cut-set}}: a set of edges whose removal disconnects the graph, for which no proper subset has the same property.}}

{{term|book}}
{{defn|no=1|A [[Book (graph theory)|book]], book graph, or triangular book is a complete tripartite graph {{math|''K''<sub>1,1,''n''</sub>}}; a collection of {{mvar|n}} triangles joined at a shared edge.}}
{{defn|no=2|Another type of graph, also called a book, or a quadrilateral book, is a collection of {{math|4}}-cycles joined at a shared edge; the Cartesian product of a star with an edge.}}
{{defn|no=3|A [[book embedding]] is an embedding of a graph onto a topological book, a space formed by joining a collection of half-planes along a shared line. Usually, the vertices of the embedding are required to be on the line, which is called the spine of the embedding, and the edges of the embedding are required to lie within a single half-plane, one of the pages of the book.}}

{{term|boundary}}
{{defn|no=1| In a [[graph embedding]], a boundary walk is the subgraph containing all incident edges and vertices to a {{gli|face}}.}}

{{term|bramble}}
{{defn|A [[Bramble (graph theory)|bramble]] is a collection of mutually touching connected subgraphs, where two subgraphs touch if they share a vertex or each includes one endpoint of an edge. The order of a bramble is the smallest size of a set of vertices that has a nonempty intersection with all of the subgraphs. The treewidth of a graph is the maximum order of any of its brambles.}}

{{term|branch}}
{{defn|A path of degree-two vertices, ending at vertices whose degree is unequal to two.<ref>{{citation
 | last = van der Holst | first = Hein
 | date = March 2009
 | doi = 10.1016/j.jctb.2008.10.002
 | issue = 2
 | journal = Journal of Combinatorial Theory, Series B
 | pages = 512–530
 | publisher = Elsevier BV
 | title = A polynomial-time algorithm to find a linkless embedding of a graph
 | volume = 99}}</ref>}}

{{term|branch-decomposition}}
{{defn|A [[branch-decomposition]] of {{mvar|G}} is a hierarchical clustering of the edges of {{mvar|G}}, represented by an unrooted binary tree with its leaves labeled by the edges of {{mvar|G}}. The width of a branch-decomposition is the maximum, over edges {{mvar|e}} of this binary tree, of the number of shared vertices between the subgraphs determined by the edges of {{mvar|G}} in the two subtrees separated by {{mvar|e}}. The branchwidth of {{mvar|G}} is the minimum width of any branch-decomposition of {{mvar|G}}.}}

{{term|branchwidth}}
{{defn|See {{gli|branch-decomposition}}.}}

{{term|bridge}}
{{defn|no=1|A [[Bridge (graph theory)|bridge]], isthmus, or cut edge is an edge whose removal would disconnect the graph. A bridgeless graph is one that has no bridges; equivalently, a 2-edge-connected graph.}}
{{defn|no=2|A bridge of a subgraph ''H'' is a maximal connected subgraph separated from the rest of the graph by ''H''.  That is, it is a maximal subgraph that is edge-disjoint from ''H'' and in which each two vertices and edges belong to a path that is internally disjoint from ''H''.  ''H'' may be a set of vertices.  A chord is a one-edge bridge.  
In [[planarity testing]], ''H'' is a cycle and a [[peripheral cycle]] is a cycle with at most one bridge; it must be a face boundary in any planar embedding of its graph.}}
{{defn|no=3|A bridge of a cycle can also mean a path that connects two vertices of a cycle but is shorter than either of the paths in the cycle connecting the same two vertices. A [[bridged graph]] is a graph in which every cycle of four or more vertices has a bridge.}}

{{term|bridgeless}}
{{defn|A [[bridgeless graph|bridgeless]] or isthmus-free graph is a graph that has no bridge edges (i.e., isthmi); that is, each connected component is a [[k-edge-connected graph|2-edge-connected graph]].}}

{{term|butterfly}}
{{defn|no=1|The [[butterfly graph]] has five vertices and six edges; it is formed by two triangles that share a vertex.}}
{{defn|no=2|The butterfly network is a graph used as a network architecture in distributed computing, closely related to the [[cube-connected cycles]].}}

{{glossary end}}

==C==
{{glossary}}

{{term|C|''C''}}
{{defn|{{math|''C''<sub>''n''</sub>}} is an {{mvar|n}}-vertex [[cycle graph]]; see {{gli|cycle}}.}}

{{term|cactus}}
{{defn|A [[cactus graph]], cactus tree, cactus, or Husimi tree is a connected graph in which each edge belongs to at most one cycle. Its blocks are cycles or single edges. If, in addition, each vertex belongs to at most two blocks, then it is called a Christmas cactus.}}

{{term|cage}}
{{defn|A [[Cage (graph theory)|cage]] is a regular graph with the smallest possible order for its girth.}}

{{term|canonical}}
{{term|canonization|multi=y}}
{{defn|A [[canonical form]] of a graph is an invariant such that two graphs have equal invariants if and only if they are isomorphic. Canonical forms may also be called canonical invariants or complete invariants, and are sometimes defined only for the graphs within a particular family of graphs. [[Graph canonization]] is the process of computing a canonical form.}}

{{term|card}}
{{defn|A graph formed from a given graph by deleting one vertex, especially in the context of the [[reconstruction conjecture]]. See also {{gli|deck}}, the multiset of all cards of a graph.}}

{{term|carving width}}
{{defn|Carving width is a notion of graph width analogous to branchwidth, but using hierarchical clusterings of vertices instead of hierarchical clusterings of edges.}}

{{term|caterpillar}}
{{defn|A [[caterpillar tree]] or caterpillar is a tree in which the internal nodes induce a path.}}

{{term|center}}
{{defn|The [[Graph center|center]] of a graph is the set of vertices of minimum {{gli|eccentricity}}.}}

{{term|centroid}}
{{defn|A [[Centroid (graph theory)|centroid]] of a tree is a vertex {{mvar|v}} such that if rooted at {{mvar|v}}, no other vertex has subtree size greater than half the size of the tree.}}

{{term|chain}}
{{defn|no=1|Synonym for {{gli|walk}}.}}
{{defn|no=2|When applying methods from [[algebraic topology]] to graphs, an element of a [[chain complex]], namely a set of vertices or a set of edges.}}

{{term|Cheeger constant}}
{{defn|See {{gli|expansion}}.}}

{{term|cherry}}
{{defn|A cherry is a path on three vertices.<ref>{{citation|last1=Sudakov|first1=Benny|last2=Volec|first2=Jan|title=Properly colored and rainbow copies of graphs with few cherries|journal=Journal of Combinatorial Theory, Series B|volume=122|issue=1|year=2017|pages=391–416|doi=10.1016/j.jctb.2016.07.001|doi-access=free|arxiv=1504.06176}}.</ref>}}

{{term|chi|''&chi;''}}
{{defn|{{math|''&chi;''(''G'')}} (using the Greek letter chi) is the chromatic number of {{mvar|G}} and {{math|''&chi;''{{hsp}}′(''G'')}} is its chromatic index; see {{gli|chromatic}} and {{gli|coloring}}.}}

{{term|child}}
{{defn|In a rooted tree, a child of a vertex {{mvar|v}} is a neighbor of {{mvar|v}} along an outgoing edge, one that is directed away from the root.}}

{{term|chord}}
{{term|chordal|multi=y}}
{{defn|no=1|A chord of a cycle is an edge that does not belong to the cycle, for which both endpoints belong to the cycle.}}
{{defn|no=2|A [[chordal graph]] is a graph in which every cycle of four or more vertices has a chord, so the only induced cycles are triangles.}}
{{defn|no=3|A [[strongly chordal graph]] is a chordal graph in which every cycle of length six or more has an odd chord.}}
{{defn|no=4|A [[chordal bipartite graph]] is not chordal (unless it is a forest); it is a bipartite graph in which every cycle of six or more vertices has a chord, so the only induced cycles are 4-cycles.}}
{{defn|no=5|A [[Chord (geometry)|chord of a circle]] is a line segment connecting two points on the circle; the [[intersection graph]] of a collection of chords is called a [[circle graph]].}}

{{term|chromatic}}
{{defn|Having to do with coloring; see {{gli|color}}. Chromatic graph theory is the theory of graph coloring. The [[chromatic number]] {{math|''&chi;''(''G'')}} is the minimum number of colors needed in a proper coloring of {{mvar|G}}. {{math|''&chi;''{{hsp}}′(''G'')}} is the [[chromatic index]] of {{mvar|G}}, the minimum number of colors needed in a proper [[edge coloring]] of {{mvar|G}}.}}

{{term|choosable}}
{{term|choosability|multi=y}}
{{defn|A graph is {{mvar|k}}-choosable if it has a [[list coloring]] whenever each vertex has a list of {{mvar|k}} available colors. The choosability of the graph is the smallest {{mvar|k}} for which it is {{mvar|k}}-choosable.}}

{{term|circle}}
{{defn|A [[circle graph]] is the [[intersection graph]] of chords of a circle.}}

{{term|circuit}}
{{defn|A circuit may refer to a closed trail or an element of the [[cycle space]] (an Eulerian spanning subgraph). The [[circuit rank]] of a graph is the dimension of its cycle space.}}

{{term|circumference}}
{{defn|The [[Circumference (graph theory)|circumference]] of a graph is the length of its longest simple cycle. The graph is Hamiltonian if and only if its circumference equals its order.}}

{{term|class}}
{{defn|no=1|A [[Class (set theory)|class]] of graphs or family of graphs is a (usually infinite) collection of graphs, often defined as the graphs having some specific property. The word "class" is used rather than "set" because, unless special restrictions are made (such as restricting the vertices to be drawn from a particular set, and defining edges to be sets of two vertices) classes of graphs are usually not sets when formalized using set theory.}}
{{defn|no=2|A color class of a colored graph is the set of vertices or edges having one particular color.}}
{{defn|no=3|In the context of [[Vizing's theorem]], on edge coloring simple graphs, a graph is said to be of class one if its chromatic index equals its maximum degree, and class two if its chromatic index equals one plus the degree. According to Vizing's theorem, all simple graphs are either of class one or class two.}}

{{term|claw}}
{{defn|A [[Claw (graph theory)|claw]] is a tree with one internal vertex and three leaves, or equivalently the complete bipartite graph {{math|''K''<sub>1,3</sub>}}. A [[claw-free graph]] is a graph that does not have an induced subgraph that is a claw.}}

{{term|clique}}
{{defn|A [[Clique (graph theory)|clique]] is a set of mutually adjacent vertices (or the complete subgraph induced by that set).  Sometimes a clique is defined as a maximal set of mutually adjacent vertices (or maximal complete subgraph), one that is not part of any larger such set (or subgraph). A {{mvar|k}}-clique is a clique of order {{mvar|k}}. The [[clique number]] {{math|''&omega;''(''G'')}} of a graph {{mvar|G}} is the order of its largest clique. The [[clique graph]] of a graph ''G'' is the [[intersection graph]] of the maximal cliques in ''G''. See also {{gli|biclique}}, a complete bipartite subgraph.}}

{{term|clique tree}}
{{defn|A synonym for a {{gli|block graph}}.}}

{{term|clique-width}}
{{defn|The [[clique-width]] of a graph {{mvar|G}} is the minimum number of distinct labels needed to construct {{mvar|G}} by operations that create a labeled vertex, form the disjoint union of two labeled graphs, add an edge connecting all pairs of vertices with given labels, or relabel all vertices with a given label. The graphs of clique-width at most {{math|2}} are exactly the [[cograph]]s.}}

{{term|closed}}
{{defn|no=1|A closed neighborhood is one that includes its central vertex; see {{gli|neighbourhood}}.}}
{{defn|no=2|A closed walk is one that starts and ends at the same vertex; see {{gli|walk}}.}}
{{defn|no=3|A graph is transitively closed if it equals its own transitive closure; see {{gli|transitive}}.}}
{{defn|no=4|A graph property is closed under some operation on graphs if, whenever the argument or arguments to the operation have the property, then so does the result. For instance, hereditary properties are closed under induced subgraphs; monotone properties are closed under subgraphs; and minor-closed properties are closed under minors.}}

{{term|closure}}
{{defn|no=1|For the transitive closure of a directed graph, see {{gli|transitive}}.}}
{{defn|no=2|A closure of a directed graph is a set of vertices that have no outgoing edges to vertices outside the closure. For instance, a sink is a one-vertex closure. The [[closure problem]] is the problem of finding a closure of minimum or maximum weight.}}

{{term|co-}}
{{defn|This prefix has various meanings usually involving [[complement graph]]s. For instance, a [[cograph]] is a graph produced by operations that include complementation; a [[cocoloring]] is a coloring in which each vertex induces either an independent set (as in proper coloring) or a clique (as in a coloring of the complement).}}

{{term|color}}
{{term|coloring|multi=y}}
{{defn|no=1|A [[graph coloring]] is a labeling of the vertices of a graph by elements from a given set of colors, or equivalently a partition of the vertices into subsets, called "color classes", each of which is associated with one of the colors.}}
{{defn|no=2|Some authors use "coloring", without qualification, to mean a proper coloring, one that assigns different colors to the endpoints of each edge. In graph coloring, the goal is to find a proper coloring that uses as few colors as possible; for instance, [[bipartite graph]]s are the graphs that have colorings with only two colors, and the [[four color theorem]] states that every [[planar graph]] can be colored with at most four colors. A graph is said to be {{mvar|k}}-colored if it has been (properly) colored with {{mvar|k}} colors, and {{mvar|k}}-colorable or {{mvar|k}}-chromatic if this is possible.}}
{{defn|no=3|Many variations of coloring have been studied, including [[edge coloring]] (coloring edges so that no two edges with the same endpoint share a color), [[list coloring]] (proper coloring with each vertex restricted to a subset of the available colors), [[acyclic coloring]] (every 2-colored subgraph is acyclic), co-coloring (every color class induces an independent set or a clique), [[complete coloring]] (every two color classes share an edge), and [[total coloring]] (both edges and vertices are colored).}}
{{defn|no=4|The coloring number of a graph is one plus the [[Degeneracy (graph theory)|degeneracy]]. It is so called because applying a greedy coloring algorithm to a degeneracy ordering of the graph uses at most this many colors.}}

{{term|comparability}}
{{defn|An undirected graph is a [[comparability graph]] if its vertices are the elements of a [[partially ordered set]] and two vertices are adjacent when they are comparable in the partial order. Equivalently, a comparability graph is a graph that has a transitive orientation. Many other classes of graphs can be defined as the comparability graphs of special types of partial order.}}

{{term|complement}}
{{defn|The [[complement graph]] <math>\bar{G}</math> of a simple graph {{mvar|G}} is another graph on the same vertex set as {{mvar|G}}, with an edge for each two vertices that are not adjacent in {{mvar|G}}.}}

{{term|complete}}
{{defn|no=1|A [[complete graph]] is one in which every two vertices are adjacent: all edges that could exist are present. A complete graph with {{mvar|n}} vertices is often denoted {{math|''K''<sub>''n''</sub>}}. A [[complete bipartite graph]] is one in which every two vertices on opposite sides of the partition of vertices are adjacent. A complete bipartite graph with {{mvar|a}} vertices on one side of the partition and {{mvar|b}} vertices on the other side is often denoted {{math|''K''<sub>''a'',''b''</sub>}}. The same terminology and notation has also been extended to [[complete multipartite graph]]s, graphs in which the vertices are divided into more than two subsets and every pair of vertices in different subsets are adjacent; if the numbers of vertices in the subsets are {{math|''a'', ''b'', ''c'', ...}} then this graph is denoted {{math|''K''<sub>''a'', ''b'', ''c'', ...</sub>}}.}}
{{defn|no=2|A completion of a given graph is a supergraph that has some desired property. For instance, a [[chordal completion]] is a supergraph that is a chordal graph.}}
{{defn|no=3|A complete matching is a synonym for a [[perfect matching]]; see {{gli|matching}}.}}
{{defn|no=4|A [[complete coloring]] is a proper coloring in which each pairs of colors is used for the endpoints of at least one edge. Every coloring with a minimum number of colors is complete, but there may exist complete colorings with larger numbers of colors. The [[achromatic number]] of a graph is the maximum number of colors in a complete coloring.}}
{{defn|no=5|A complete invariant of a graph is a synonym for a canonical form, an invariant that has different values for non-isomorphic graphs.}}

{{term|component}}
{{defn|A [[Connected component (graph theory)|connected component]] of a graph is a maximal connected subgraph. The term is also used for maximal subgraphs or subsets of a graph's vertices that have some higher order of connectivity, including [[biconnected component]]s, [[triconnected component]]s, and [[strongly connected component]]s.}}

{{term|condensation}}
{{defn|The [[Condensation (graph theory)|condensation]] of a directed graph {{mvar|G}} is a directed acyclic graph with one vertex for each strongly connected component of {{mvar|G}}, and an edge connecting pairs of components that contain the two endpoints of at least one edge in {{mvar|G}}.}}

{{term|cone}}
{{defn|A graph that contains a [[universal vertex]].}}

{{term|connect}}
{{defn|Cause to be {{gli|connected}}.}}

{{term|connected}}
{{defn|A [[Connectivity (graph theory)|connected graph]] is one in which each pair of vertices forms the endpoints of a path. Higher forms of connectivity include strong connectivity in directed graphs (for each two vertices there are paths from one to the other in both directions), [[k-vertex-connected graph|{{mvar|k}}-vertex-connected graphs]] (removing fewer than {{mvar|k}} vertices cannot disconnect the graph), and [[k-edge-connected graph|{{mvar|k}}-edge-connected graphs]] (removing fewer than {{mvar|k}} edges cannot disconnect the graph).}}

{{term|connected component}}
{{defn|Synonym for {{gli|component}}.}}

{{term|contraction}}
{{defn|[[Edge contraction]] is an elementary operation that removes an edge from a graph while merging the two vertices that it previously joined. Vertex contraction (sometimes called vertex identification) is similar, but the two vertices are not necessarily connected by an edge. Path contraction occurs upon the set of edges in a path that contract to form a single edge between the endpoints of the path. The inverse of edge contraction is vertex splitting.}}

{{term|converse}}
{{defn|The converse graph is a synonym for the transpose graph; see {{gli|transpose}}.}}

{{term|core}}
{{defn|no=1|A [[k-core|{{mvar|k}}-core]] is the induced subgraph formed by removing all vertices of degree less than {{mvar|k}}, and all vertices whose degree becomes less than {{mvar|k}} after earlier removals. See {{gli|degeneracy}}.}}
{{defn|no=2|A [[Core (graph theory)|core]] is a graph {{mvar|G}} such that every [[graph homomorphism]] from {{mvar|G}} to itself is an isomorphism.}}
{{defn|no=3|The [[Core (graph theory)|core]] of a graph {{mvar|G}} is a minimal graph {{mvar|H}} such that there exist homomorphisms from {{mvar|G}} to {{mvar|H}} and vice versa. {{mvar|H}} is unique up to isomorphism. It can be represented as an induced subgraph of {{mvar|G}}, and is a core in the sense that all of its self-homomorphisms are isomorphisms.}}
{{defn|no=4|In the theory of graph matchings, the core of a graph is an aspect of its [[Dulmage–Mendelsohn decomposition]], formed as the union of all maximum matchings.}}

{{term|cotree}}
{{defn|no=1|The complement of a [[spanning tree]].}}
{{defn|no=2|A rooted tree structure used to describe a [[cograph]], in which each cograph vertex is a leaf of the tree, each internal node of the tree is labeled with 0 or 1, and two cograph vertices are adjacent if and only if their lowest common ancestor in the tree is labeled 1.}}

{{term|cover}}
{{defn|A [[vertex cover]] is a set of vertices incident to every edge in a graph. An [[edge cover]] is a set of edges incident to every vertex in a graph. A set of subgraphs of a graph covers that graph if its [[Graph operations#Binary operations|union]] – taken vertex-wise and edge-wise – is equal to the graph.}}

{{term|critical}}
{{defn|A critical graph for a given property is a graph that has the property but such that every subgraph formed by deleting a single vertex does not have the property. For instance, a [[factor-critical graph]] is one that has a perfect matching (a 1-factor) for every vertex deletion, but (because it has an odd number of vertices) has no perfect matching itself. Compare ''hypo-'', used for graphs which do not have a property but for which every one-vertex deletion does.}}

{{term|cube}}
{{term|cubic|multi=y}}
{{defn|no=1|[[Cube graph]], the eight-vertex graph of the vertices and edges of a cube.}}
{{defn|no=2|[[Hypercube graph]], a higher-dimensional generalization of the cube graph.}}
{{defn|no=3|[[Folded cube graph]], formed from a hypercube by adding a matching connecting opposite vertices.}}
{{defn|no=4|[[Halved cube graph]], the [[half-square]] of a hypercube graph.}}
{{defn|no=5|[[Partial cube]], a distance-preserving subgraph of a hypercube.}}
{{defn|no=6|The cube of a graph {{mvar|G}} is the [[graph power]] {{math|''G''<sup>3</sup>}}.}}
{{defn|no=7|[[Cubic graph]], another name for a {{math|3}}-regular graph, one in which each vertex has three incident edges.}}
{{defn|no=8|[[Cube-connected cycles]], a cubic graph formed by replacing each vertex of a hypercube by a cycle.}}

{{term|cut}}
{{term|cut-set|multi=y}}
{{defn|A [[cut (graph theory)|cut]] is a partition of the vertices of a graph into two subsets, or the set (also known as a cut-set) of edges that span such a partition, if that set is non-empty. An edge is said to span the partition if it has endpoints in both subsets. Thus, the removal of a cut-set from a connected graph disconnects it.}}

{{term|cut point}}
{{defn|See {{gli|articulation point}}.}}

{{term|cut space}}
{{defn|The [[cut space]] of a graph is a [[GF(2)]]-[[vector space]] having the {{gli|cut-set}}s of the graph as its elements and [[symmetric difference]] of sets as its vector addition operation.}}

{{term|cycle}}
{{defn|no=1|A [[Cycle (graph theory)|cycle]] may be either a kind of graph or a kind of {{gli|walk}}.  As a walk it may be either be a closed walk (also called a {{gli|tour}}) or more usually a closed walk without repeated vertices and consequently edges (also called a simple cycle). In the latter case it is usually regarded as a graph, i.e., the choices of first vertex and direction are usually considered unimportant; that is, [[cyclic permutation]]s and reversals of the walk produce the same cycle. Important special types of cycle include [[Hamiltonian cycle]]s, [[induced cycle]]s, [[peripheral cycle]]s, and the shortest cycle, which defines the [[Girth (graph theory)|girth]] of a graph. A {{mvar|k}}-cycle is a cycle of length {{mvar|k}}; for instance a {{mvar|2}}-cycle is a [[digon]] and a {{math|3}}-cycle is a triangle. A [[cycle graph]] is a graph that is itself a simple cycle; a cycle graph with {{mvar|n}} vertices is commonly denoted {{math|''C''<sub>''n''</sub>}}. }}
{{defn|no=2|The [[cycle space]] is a [[vector space]] generated by the simple cycles in a graph, often over the field of 2 elements but also over other fields.}}

{{glossary end}}

==D==
{{glossary}}

{{term|DAG}}
{{defn|Abbreviation for [[directed acyclic graph]], a directed graph without any directed cycles.}}

{{term|deck}}
{{defn|The multiset of graphs formed from a single graph {{mvar|G}} by deleting a single vertex in all possible ways, especially in the context of the [[reconstruction conjecture]]. An edge-deck is formed in the same way by deleting a single edge in all possible ways. The graphs in a deck are also called ''cards''. See also {{gli|critical}} (graphs that have a property that is not held by any card) and {{gli|hypo-}} (graphs that do not have a property that is held by all cards).}}

{{term|decomposition}}
{{defn|See {{gli|tree decomposition}}, {{gli|path decomposition}}, or {{gli|branch-decomposition}}.}}

{{term|degenerate}}
{{term|degeneracy|multi=y}}
{{defn|A {{mvar|k}}-degenerate graph is an undirected graph in which every induced subgraph has minimum degree at most {{mvar|k}}. The [[Degeneracy (graph theory)|degeneracy]] of a graph is the smallest {{mvar|k}} for which it is {{mvar|k}}-degenerate. A degeneracy ordering is an ordering of the vertices such that each vertex has minimum degree in the induced subgraph of it and all later vertices; in a degeneracy ordering of a {{mvar|k}}-degenerate graph, every vertex has at most {{mvar|k}} later neighbours. Degeneracy is also known as the {{mvar|k}}-core number, width, and linkage, and one plus the degeneracy is also called the coloring number or Szekeres–Wilf number. {{mvar|k}}-degenerate graphs have also been called {{mvar|k}}-inductive graphs.}}

{{term|degree}}
{{defn|no=1|The [[degree (graph theory)|degree]] of a vertex in a graph is its number of incident edges.<ref name="clrs"/> The degree of a graph {{mvar|G}} (or its maximum degree) is the maximum of the degrees of its vertices, often denoted {{math|&Delta;(''G'')}}; the minimum degree of {{mvar|G}} is the minimum of its vertex degrees, often denoted {{math|''&delta;''(''G'')}}. Degree is sometimes called ''valency''; the degree of {{mvar|v}} in {{mvar|G}} may be denoted {{math|''d''<sub>''G''</sub>(''v'')}}, {{math|''d''(''G'')}}, or {{math|deg(''v'')}}. The total degree is the sum of the degrees of all vertices; by the [[handshaking lemma]] it is an even number. The [[degree sequence]] is the collection of degrees of all vertices, in sorted order from largest to smallest. In a directed graph, one may distinguish the in-degree (number of incoming edges) and out-degree (number of outgoing edges).<ref name="clrs"/>}}
{{defn|no=2|The homomorphism degree of a graph is a synonym for its ''Hadwiger number'', the order of the largest clique minor.}}

{{term|delta|&Delta;, ''&delta;''}}
{{defn|{{math|&Delta;(''G'')}} (using the Greek letter delta) is the maximum degree of a vertex in {{mvar|G}}, and {{math|''&delta;''(''G'')}} is the minimum degree; see {{gli|degree}}.}}

{{term|density}}
{{defn|In a graph of ''n'' nodes, the density is the ratio of the number of edges of the graph to the number of edges in a complete graph on ''n'' nodes. See [[dense graph]].}}

{{term|depth}}
{{defn|The depth of a node in a rooted tree is the number of edges in the path from the root to the node. For instance, the depth of the root is 0 and the depth of any one of its adjacent nodes is 1. It is the level of a node minus one. Note, however, that some authors instead use ''depth'' as a synonym for the ''level'' of a node.<ref>{{citation|url=https://xlinux.nist.gov/dads/HTML/depth.html|title=depth|publisher = [[NIST]]}}</ref>}}

{{term|diameter}}
{{defn|The [[diameter (graph theory)|diameter]] of a connected graph is the maximum length of a [[shortest path]]. That is, it is the maximum of the distances between pairs of vertices in the graph. If the graph has weights on its edges, then its weighted diameter measures path length by the sum of the edge weights along a path, while the unweighted diameter measures path length by the number of edges.
For disconnected graphs, definitions vary: the diameter may be defined as infinite, or as the largest diameter of a connected component, or it may be undefined.}}

{{term|diamond}}
{{defn|The [[diamond graph]] is an undirected graph with four vertices and five edges.}}

{{term|diconnected}}
{{defn|{{gli|Strong}}ly {{gli|connected}}. (Not to be confused with {{gli|disconnected}})}}

{{term|digon}}
{{defn|A [[digon]] is a simple cycle of length two in a directed graph or a multigraph. Digons cannot occur in [[Simple graph|simple]] undirected graphs as they require repeating the same edge twice, which violates the definition of [[Simple graph|simple]].}}

{{term|digraph}}
{{defn|Synonym for [[directed graph]].<ref name="clrs"/>}}

{{term|dipath}}
{{defn|See {{gli|directed path}}.}}

{{term|direct predecessor}}
{{defn|The tail of a directed edge whose head is the given vertex.}}

{{term|direct successor}}
{{defn|The head of a directed edge whose tail is the given vertex.}}

{{term|directed}}
{{defn|A [[directed graph]] is one in which the edges have a distinguished direction, from one vertex to another.<ref name="clrs"/> In a [[mixed graph]], a directed edge is again one that has a distinguished direction; directed edges may also be called arcs or arrows.}}

{{term|directed arc}}
{{defn|See {{gli|arrow}}.}}

{{term|directed edge}}
{{defn|See {{gli|arrow}}.}}

{{term|directed line}}
{{defn|See {{gli|arrow}}.}}

{{term|directed path}}
{{defn|A {{gli|path}} in which all the ''{{gli|edge}}s'' have the same {{gli|direction}}. If a directed path leads from {{gli|vertex}} {{math|''x''}} to vertex {{math|''y''}}, {{math|''x''}} is a {{gli|predecessor}} of {{math|''y''}}, {{math|''y''}} is a {{gli|successor}} of  {{math|''x''}}, and {{math|''y''}} is said to be {{gli|reachable}} from {{math|''x''}}.}}

{{term|direction}}
{{defn|no=1|The [[asymmetric relation]] between two {{gli|adjacent}} {{gli|vertex|vertices}} in a {{gli|graph}}, represented as an {{gli|arrow}}.}}
{{defn|no=2|The asymmetric relation between two vertices in a {{gli|directed path}}.}}

{{term|disconnect}}
{{defn|Cause to be {{gli|disconnected}}.}}

{{term|disconnected}}
{{defn|Not {{gli|connected}}.}}

{{term|disjoint}}
{{defn|no=1|Two subgraphs are edge disjoint if they share no edges, and vertex disjoint if they share no vertices.}}
{{defn|no=2|The disjoint union of two or more graphs is a graph whose vertex and edge sets are the [[disjoint union]]s of the corresponding sets.}}

{{term|dissociation number}}
{{defn|A subset of vertices in a graph ''G'' is called ''dissociation'' if it induces a [[Glossary of graph theory#subgraph|subgraph]] with maximum [[Degree (graph theory)|degree]] 1.}}

{{term|distance}}
{{defn|The [[Distance (graph theory)|distance]] between any two vertices in a graph is the length of the shortest path having the two vertices as its endpoints.}}

{{term|domatic}}
{{defn|A domatic partition of a graph is a partition of the vertices into dominating sets. The [[domatic number]] of the graph is the maximum number of dominating sets in such a partition.}}

{{term|dominating}}
{{defn|A [[dominating set]] is a set of vertices that includes or is adjacent to every vertex in the graph; not to be confused with a vertex cover, a vertex set that is incident to all edges in the graph. Important special types of dominating sets include independent dominating sets (dominating sets that are also independent sets) and connected dominating sets (dominating sets that induced connected subgraphs). A single-vertex dominating set may also be called a universal vertex. The domination number of a graph is the number of vertices in the smallest dominating set.}}

{{Term|dual}}{{Defn|A [[dual graph]] of a plane graph {{mvar|G}} is a graph that has a vertex for each face of {{mvar|G}}.}}{{glossary end}}

==E==
{{glossary}}

{{term|E|''E''}}
{{defn|{{math|''E''(''G'')}} is the edge set of {{mvar|G}}; see {{gli|edge set}}.}}

{{term|ear}}
{{defn|An ear of a graph is a path whose endpoints may coincide but in which otherwise there are no repetitions of vertices or edges.}}

{{term|ear decomposition}}
{{defn|An [[ear decomposition]] is a partition of the edges of a graph into a sequence of ears, each of whose endpoints (after the first one) belong to a previous ear and each of whose interior points do not belong to any previous ear. An open ear is a simple path (an ear without repeated vertices), and an open ear decomposition is an ear decomposition in which each ear after the first is open; a graph has an open ear decomposition if and only if it is biconnected. An ear is odd if it has an odd number of edges, and an odd ear decomposition is an ear decomposition in which each ear is odd; a graph has an odd ear decomposition if and only if it is factor-critical.}}

{{term|eccentricity}}
{{defn|The eccentricity of a vertex is the farthest distance from it to any other vertex.}}

{{term|edge}}
{{defn|An edge is (together with vertices) one of the two basic units out of which graphs are constructed. Each edge has two (or in hypergraphs, more) vertices to which it is attached, called its endpoints. Edges may be directed or undirected; undirected edges are also called lines and directed edges are also called arcs or arrows. In an undirected [[simple graph]], an edge may be represented as the set of its vertices, and in a directed simple graph it may be represented as an ordered pair of its vertices. An edge that connects vertices {{mvar|x}} and {{mvar|y}} is sometimes written {{mvar|xy}}.}}

{{term|edge cut}}
{{defn|A set of {{gli|edge}}s whose removal {{gli|disconnected|disconnects}} the {{gli|graph}}. A one-edge cut is called a {{gli|bridge}}, {{gli|isthmus}}, or {{gli|cut edge}}.}}

{{term|edge set}}
{{defn|The set of edges of a given graph {{mvar|G}}, sometimes denoted by {{math|''E''(''G'')}}.}}

{{term|edgeless graph}}
{{defn|The [[edgeless graph]] or totally disconnected graph on a given set of vertices is the graph that has no edges. It is sometimes called the empty graph, but this term can also refer to a graph with no vertices.}}

{{term|embedding}}
{{defn|A [[graph embedding]] is a topological representation of a graph as a subset of a topological space with each vertex represented as a point, each edge represented as a curve having the endpoints of the edge as endpoints of the curve, and no other intersections between vertices or edges. A [[planar graph]] is a graph that has such an embedding onto the Euclidean plane, and a [[toroidal graph]] is a graph that has such an embedding onto a torus. The [[Genus (mathematics)|genus]] of a graph is the minimum possible genus of a two-dimensional [[manifold]] onto which it can be embedded.}}

{{term|empty graph}}
{{defn|no=1|An [[edgeless graph]] on a nonempty set of vertices.}}
{{defn|no=2|The [[order-zero graph]], a graph with no vertices and no edges.}}

{{term|end}}
{{defn|An [[End (graph theory)|end]] of an infinite graph is an equivalence class of rays, where two rays are equivalent if there is a third ray that includes infinitely many vertices from both of them.}}

{{term|endpoint}}
{{defn|One of the two vertices joined by a given edge, or one of the first or last vertex of a walk, trail or path. The first endpoint of a given directed edge is called the ''tail'' and the second endpoint is called the ''head''.}}

{{term|enumeration}}
{{defn|[[Graph enumeration]] is the problem of counting the graphs in a given class of graphs, as a function of their order. More generally, enumeration problems can refer either to problems of counting a certain class of combinatorial objects (such as cliques, independent sets, colorings, or spanning trees), or of algorithmically listing all such objects.}}

{{term|Eulerian}}
{{defn|An [[Eulerian path]] is a walk that uses every edge of a graph exactly once. An Eulerian circuit (also called an Eulerian cycle or an Euler tour) is a closed walk that uses every edge exactly once. An Eulerian graph is a graph that has an Eulerian circuit. For an undirected graph, this means that the graph is connected and every vertex has even degree. For a directed graph, this means that the graph is strongly connected and every vertex has in-degree equal to the out-degree. In some cases, the connectivity requirement is loosened, and a graph meeting only the degree requirements is called Eulerian.}}

{{term|even}}
{{defn|Divisible by two; for instance, an even cycle is a cycle whose length is even.}}

{{term|expander}}
{{defn|An [[expander graph]] is a graph whose edge expansion, vertex expansion, or spectral expansion is bounded away from zero.}}

{{term|expansion}}
{{defn|no=1|The edge expansion, isoperimetric number, or [[Cheeger constant (graph theory)|Cheeger constant]] of a graph {{mvar|G}} is the minimum ratio, over subsets {{mvar|S}} of at most half of the vertices of {{mvar|G}}, of the number of edges leaving {{mvar|S}} to the number of vertices in {{mvar|S}}.}}
{{defn|no=2|The vertex expansion, vertex isoperimetric number, or magnification of a graph {{mvar|G}} is the minimum ratio, over subsets {{mvar|S}} of at most half of the vertices of {{mvar|G}}, of the number of vertices outside but adjacent to {{mvar|S}} to the number of vertices in {{mvar|S}}.}}
{{defn|no=3|The unique neighbor expansion of a graph {{mvar|G}} is the minimum ratio, over subsets of at most half of the vertices of {{mvar|G}}, of the number of vertices outside {{mvar|S}} but adjacent to a unique vertex in {{mvar|S}} to the number of vertices in {{mvar|S}}.}}
{{defn|no=4|The spectral expansion of a {{mvar|d}}-regular graph {{mvar|G}} is the [[spectral gap]] between the largest eigenvalue {{mvar|d}} of its adjacency matrix and the second-largest eigenvalue.}}
{{defn|no=5|A family of graphs has [[bounded expansion]] if all its {{mvar|r}}-shallow minors have a ratio of edges to vertices bounded by a function of {{mvar|r}}, and polynomial expansion if the function of {{mvar|r}} is a polynomial.}}

{{glossary end}}

==F==
{{glossary}}

{{term|face}}
{{defn|In a [[planar graph|plane graph]] or [[graph embedding]], a connected component of the subset of the plane or surface of the embedding that is disjoint from the graph. For an embedding in the plane, all but one face will be bounded; the one exceptional face that extends to infinity is called the outer (or infinite) face.}}

{{term|factor}}
{{defn|A factor of a graph is a spanning subgraph: a subgraph that includes all of the vertices of the graph. The term is primarily used in the context of regular subgraphs: a {{mvar|k}}-factor is a factor that is {{mvar|k}}-regular. In particular, a {{math|1}}-factor is the same thing as a perfect matching. A [[factor-critical graph]] is a graph for which deleting any one vertex produces a graph with a {{math|1}}-factor.}}

{{term|factorization}}
{{defn|A [[graph factorization]] is a partition of the edges of the graph into factors; a {{mvar|k}}-factorization is a partition into {{mvar|k}}-factors. For instance a {{math|1}}-factorization is an edge coloring with the additional property that each vertex is incident to an edge of each color.}}

{{term|family}}
{{defn|A synonym for {{gli|class}}.}}

{{term|finite}}
{{defn|A graph is finite if it has a finite number of vertices and a finite number of edges. Many sources assume that all graphs are finite without explicitly saying so. A graph is locally finite if each vertex has a finite number of incident edges. An infinite graph is a graph that is not finite: it has infinitely many vertices, infinitely many edges, or both.}}

{{term|first order}}
{{defn|The first order [[logic of graphs]] is a form of logic in which variables represent vertices of a graph, and there exists a binary predicate to test whether two vertices are adjacent. To be distinguished from second order logic, in which variables can also represent sets of vertices or edges.}}

{{term|-flap}}
{{defn|For a set of vertices {{mvar|X}}, an {{mvar|X}}-flap is a connected component of the induced subgraph formed by deleting {{mvar|X}}. The flap terminology is commonly used in the context of ''havens'', functions that map small sets of vertices to their flaps. See also the {{gli|bridge}} of a cycle, which is either a flap of the cycle vertices or a chord of the cycle.}}

{{term|forbidden}}
{{defn|A [[forbidden graph characterization]] is a characterization of a family of graphs as being the graphs that do not have certain other graphs as subgraphs, induced subgraphs, or minors. If {{mvar|H}} is one of the graphs that does not occur as a subgraph, induced subgraph, or minor, then {{mvar|H}} is said to be forbidden.}}

{{term|forcing graph}}
{{defn|A [[forcing graph]] is a graph {{mvar|H}} such that evaluating the subgraph density of {{mvar|H}} in the graphs of a graph sequence {{mvar|G(n)}} is sufficient to test whether that sequence is {{gli|quasi-random graph sequence|quasi-random}}.}}

{{term|forest}}
{{defn|A [[Tree (graph theory)|forest]] is an undirected graph without cycles (a disjoint union of unrooted trees), or a directed graph formed as a disjoint union of rooted trees.}}

{{term|free edge}}
{{defn|An [[Edge (graph theory)|edge]] which is not in a [[matching (graph theory)|matching]].}}

{{term|free vertex}}
{{defn|no=1|A [[Vertex (graph theory)|vertex]] not on a matched [[Edge (graph theory)|edge]] in a [[matching (graph theory)|matching]]}}
{{defn|no=2|A vertex which has not been matched.}}

{{term|Frucht}}
{{defn|no=1|[[Robert Frucht]]}}
{{defn|no=2|The [[Frucht graph]], one of the two smallest cubic graphs with no nontrivial symmetries.}}
{{defn|no=3|[[Frucht's theorem]] that every finite group is the group of symmetries of a finite graph.}}

{{term|full}}
{{defn|Synonym for {{gli|induced}}.}}

{{term|functional graph}}
{{defn|A [[functional graph]] is a directed graph where every vertex has out-degree one.  Equivalently, a functional graph is a maximal directed pseudoforest.}}

{{glossary end}}

==G==
{{glossary}}

{{term|G|''G''}}
{{defn|A variable often used to denote a graph.}}

{{term|genus}}
{{defn|The genus of a graph is the minimum genus of a surface onto which it can be embedded; see {{gli|embedding}}.}}

{{term|geodesic}}
{{defn|As a noun, a geodesic is a synonym for a [[shortest path]]. When used as an adjective, it means related to shortest paths or shortest path distances.}}

{{term|giant}}
{{defn|In the theory of [[random graph]]s, a giant component is a connected component that contains a constant fraction of the vertices of the graph. In standard models of random graphs, there is typically at most one giant component.}}

{{term|girth}}
{{defn|The [[Girth (graph theory)|girth]] of a graph is the length of its shortest cycle.}}

{{term|graph}}
{{defn|The fundamental object of study in graph theory, a system of vertices connected in pairs by edges. Often subdivided into [[directed graph]]s or [[undirected graph]]s according to whether the edges have an orientation or not. [[Mixed graph]]s include both types of edges.}}

{{term|greedy}}
{{defn|Produced by a [[greedy algorithm]]. For instance, a [[greedy coloring]] of a graph is a coloring produced by considering the vertices in some sequence and assigning each vertex the first available color.}}

{{term|Grötzsch}}
{{defn|no=1|[[Herbert Grötzsch]]}}
{{defn|no=2|The [[Grötzsch graph]], the smallest triangle-free graph requiring four colors in any proper coloring.}}
{{defn|no=3|[[Grötzsch's theorem]] that triangle-free planar graphs can always be colored with at most three colors.}}

{{term|Grundy number}}
{{defn|no=1|The [[Grundy number]] of a graph is the maximum number of colors produced by a [[greedy coloring]], with a badly-chosen vertex ordering.}}

{{glossary end}}

==H==
{{glossary}}

{{term|H|''H''}}
{{defn|A variable often used to denote a graph, especially when another graph has already been denoted by {{mvar|G}}.}}

{{term|H-coloring|''H''-coloring}}
{{defn|An {{mvar|H}}-coloring of a graph {{mvar|G}} (where {{mvar|H}} is also a graph) is a homomorphism from {{mvar|H}} to {{mvar|G}}.}}

{{term|H-tree|''H''-free}}
{{defn|A graph is {{mvar|H}}-free if it does not have an induced subgraph isomorphic to {{mvar|H}}, that is, if {{mvar|H}} is a forbidden induced subgraph. The {{mvar|H}}-free graphs are the family of all graphs (or, often, all finite graphs) that are {{mvar|H}}-free.<ref>{{citation
 | last1 = Brandstädt
 | first1 = Andreas
 | author1-link = Andreas Brandstädt
 | last2 = Le
 | first2 = Van Bang
 | last3 = Spinrad
 | first3 = Jeremy
 | contribution = Chapter 7: Forbidden Subgraph
 | pages = [https://archive.org/details/graphclassessurv0000bran/page/105 105–121]
 | title = Graph Classes: A Survey
 | publisher = SIAM Monographs on Discrete Mathematics and Applications
 | year = 1999
 | isbn = 978-0-89871-432-6
 | url = https://archive.org/details/graphclassessurv0000bran/page/105
 }}</ref> For instance the [[triangle-free graph]]s are the graphs that do not have a [[triangle graph]] as a subgraph. The property of being {{mvar|H}}-free is always hereditary. A graph is {{mvar|H}}-minor-free if it does not have a minor isomorphic to {{mvar|H}}.}}

{{term|Hadwiger}}
{{defn|no=1|[[Hugo Hadwiger]]}}
{{defn|no=2|The [[Hadwiger number]] of a graph is the order of the largest complete minor of the graph. It is also called the contraction clique number or the homomorphism degree.}}
{{defn|no=3|The [[Hadwiger conjecture (graph theory)|Hadwiger conjecture]] is the conjecture that the Hadwiger number is never less than the chromatic number.}}

{{term|Hamiltonian}}
{{defn|A [[Hamiltonian path]] or Hamiltonian cycle is a simple spanning path or simple spanning cycle: it covers all of the vertices in the graph exactly once. A graph is Hamiltonian if it contains a Hamiltonian cycle, and traceable if it contains a Hamiltonian path.}}

{{term|haven}}
{{defn|A {{mvar|k}}-[[Haven (graph theory)|haven]] is a function that maps every set {{mvar|X}} of fewer than {{mvar|k}} vertices to one of its flaps, often satisfying additional consistency conditions. The order of a haven is the number {{mvar|k}}. Havens can be used to characterize the treewidth of finite graphs and the ends and Hadwiger numbers of infinite graphs.}}

{{term|height}}
{{defn|no=1|The ''height'' of a node in a rooted tree is the number of edges in a longest path, going away from the root (i.e. its nodes have strictly increasing depth), that starts at that node and ends at a leaf.}}
{{defn|no=2|The ''height'' of a rooted tree is the height of its root. That is, the ''height'' of a tree is the number of edges in a longest possible path, going away from the root, that starts at the root and ends at a leaf.}}
{{defn|no=3|The ''height'' of a [[directed acyclic graph]] is the maximum length of a directed path in this graph.}}

{{term|hereditary}}
{{defn|A [[hereditary property]] of graphs is a property that is closed under induced subgraphs: if {{mvar|G}} has a hereditary property, then so must every induced subgraph of {{mvar|G}}. Compare {{gli|monotone}} (closed under all subgraphs) or ''minor-closed'' (closed under minors).}}

{{term|[[hexagon]]}}
{{defn|A simple cycle consisting of exactly six edges and six vertices.}}

{{term|hole}}
{{defn|A hole is an induced cycle of length four or more. An odd hole is a hole of odd length. An anti-hole is an induced subgraph of order four whose complement is a cycle; equivalently, it is a hole in the complement graph. This terminology is mainly used in the context of perfect graphs, which are characterized by the [[strong perfect graph theorem]] as being the graphs with no odd holes or odd anti-holes. The hole-free graphs are the same as the [[chordal graph]]s.}}

{{term|homomorphic equivalence}}
{{defn|Two graphs are [[Graph homomorphism|homomorphically equivalent]] if there exist two homomorphisms, one from each graph to the other graph.}}

{{term|homomorphism}}
{{defn|no=1|A [[graph homomorphism]] is a mapping from the vertex set of one graph to the vertex set of another graph that maps adjacent vertices to adjacent vertices. This type of mapping between graphs is the one that is most commonly used in category-theoretic approaches to graph theory. A proper graph coloring can equivalently be described as a homomorphism to a complete graph.}}
{{defn|no=2|The homomorphism degree of a graph is a synonym for its ''Hadwiger number'', the order of the largest clique minor.}}

{{term|hyperarc}}
{{defn|A directed {{gli|hyperedge}} having a source and target set.}}

{{term|hyperedge}}
{{defn|An {{gli|edge}} in a {{gli|hypergraph}}, having any number of endpoints, in contrast to the requirement that edges of graphs have exactly two endpoints.}}

{{term|hypercube}}
{{defn|A [[hypercube graph]] is a graph formed from the vertices and edges of a geometric [[hypercube]].}}

{{term|hypergraph}}
{{defn|A [[hypergraph]] is a generalization of a graph in which each edge (called a hyperedge in this context) may have more than two endpoints.}}

{{term|hypo-}}
{{defn|This prefix, in combination with a graph property, indicates a graph that does not have the property but such that every subgraph formed by deleting a single vertex does have the property. For instance, a [[hypohamiltonian graph]] is one that does not have a Hamiltonian cycle, but for which every one-vertex deletion produces a Hamiltonian subgraph. Compare {{gli|critical}}, used for graphs which have a property but for which every one-vertex deletion does not.<ref>{{citation
 | last = Mitchem | first = John
 | contribution = Hypo-properties in graphs
 | doi = 10.1007/BFb0060121
 | mr = 0253932
 | pages = 223–230
 | publisher = Springer
 | title = The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968)
 | volume = 110
 | year = 1969| series = Lecture Notes in Mathematics
 | isbn = 978-3-540-04629-5
 }}.</ref>}}

{{glossary end}}

==I==
{{glossary}}

{{term|in-degree}}
{{defn|The number of incoming edges in a directed graph; see {{gli|degree}}.}}

{{term|incidence}}
{{defn|An [[Incidence (graph)|incidence]] in a graph is a vertex-edge pair such that the vertex is an endpoint of the edge.}}

{{term|incidence matrix}}
{{defn|The [[incidence matrix]] of a graph is a matrix whose rows are indexed by vertices of the graph, and whose columns are indexed by edges, with a one in the cell for row {{mvar|i}} and column {{mvar|j}} when vertex {{mvar|i}} and edge {{mvar|j}} are incident, and a zero otherwise.}}

{{term|incident}}
{{defn|The relation between an edge and one of its endpoints.<ref name="clrs"/>}}

{{term|incomparability}}
{{defn|An incomparability graph is the complement of a [[comparability graph]]; see {{gli|comparability}}.}}

{{term|independent}}
{{defn|no=1|An [[Independent set (graph theory)|independent set]] is a set of vertices that induces an edgeless subgraph. It may also be called a stable set or a coclique. The [[independence number]] {{math|''&alpha;''(''G'')}} is the size of the [[maximum independent set]].}}
{{defn|no=2|In the [[graphic matroid]] of a graph, a subset of edges is independent if the corresponding subgraph is a tree or forest. In the [[bicircular matroid]], a subset of edges is independent if the corresponding subgraph is a [[pseudoforest]].}}

{{term|indifference}}
{{defn|An [[indifference graph]] is another name for a proper interval graph or unit interval graph; see {{gli|proper}}.}}

{{term|induced}}
{{defn|An [[induced subgraph]] or full subgraph of a graph is a subgraph formed from a subset of vertices and from all of the edges that have both endpoints in the subset. Special cases include [[induced path]]s and [[induced cycle]]s, induced subgraphs that are paths or cycles.}}

{{term|inductive}}
{{defn|Synonym for {{gli|degenerate}}.}}

{{term|infinite}}
{{defn|An infinite graph is one that is not finite; see {{gli|finite}}.}}

{{term|internal}}
{{defn|A vertex of a path or tree is internal if it is not a leaf; that is, if its degree is greater than one. Two paths are internally disjoint (some people call it ''independent'') if they do not have any vertex in common, except the first and last ones.}}

{{term|intersection}}
{{defn|no=1|The intersection of two graphs is their largest common subgraph, the graph formed by the vertices and edges that belong to both graphs.}}
{{defn|no=2|An [[intersection graph]] is a graph whose vertices correspond to sets or geometric objects, with an edge between two vertices exactly when the corresponding two sets or objects have a nonempty intersection. Several classes of graphs may be defined as the intersection graphs of certain types of objects, for instance [[chordal graph]]s (intersection graphs of subtrees of a tree), [[circle graph]]s (intersection graphs of chords of a circle), [[interval graph]]s (intersection graphs of intervals of a line), [[line graph]]s (intersection graphs of the edges of a graph), and [[clique graph]]s (intersection graphs of the maximal cliques of a graph). Every graph is an intersection graph for some family of sets, and this family is called an intersection representation of the graph. The [[intersection number (graph theory)|intersection number]] of a graph {{mvar|G}} is the minimum total number of elements in any intersection representation of {{mvar|G}}.}}

{{term|interval}}
{{defn|no=1|An [[interval graph]] is an [[intersection graph]] of [[Interval (mathematics)|intervals of a line]].}}
{{defn|no=2|The interval {{math|[''u'', ''v'']}} in a graph is the union of all shortest paths from {{mvar|u}} to {{mvar|v}}.}}
{{defn|no=3|Interval thickness is a synonym for {{gli|pathwidth}}.}}

{{term|invariant}}
{{defn|A synonym of {{gli|property}}.}}

{{term|inverted arrow}}
{{defn|An {{gli|arrow}} with an opposite {{gli|direction}} compared to another arrow. The arrow {{math|(''y'', ''x'')}} is the inverted arrow of the arrow {{math|(''x'', ''y'')}}.}}

{{term|isolated}}
{{defn|An isolated vertex of a graph is a vertex whose degree is zero, that is, a vertex with no incident edges.<ref name="clrs"/>}}

{{term|isomorphic}}
{{defn|Two graphs are isomorphic if there is an isomorphism between them; see {{gli|isomorphism}}.}}

{{term|isomorphism}}
{{defn|A [[graph isomorphism]] is a one-to-one incidence preserving correspondence of the vertices and edges of one graph to the vertices and edges of another graph. Two graphs related in this way are said to be isomorphic.}}

{{term|isoperimetric}}
{{defn|See {{gli|expansion}}.}}

{{term|isthmus}}
{{defn|Synonym for {{gli|bridge}}, in the sense of an edge whose removal disconnects the graph.}}

{{glossary end}}

==J==
{{glossary}}

{{term|join}}
{{defn|The [[Graph operations#Binary operations|join]] of two graphs is formed from their [[#disjoint|disjoint union]] by adding an edge from each vertex of one graph to each vertex of the other. Equivalently, it is the complement of the disjoint union of the complements.}}
{{glossary end}}

==K==
{{glossary}}

{{term|K|''K''}}
{{defn|For the notation for complete graphs, complete bipartite graphs, and complete multipartite graphs, see {{gli|complete}}.}}

{{term|kappa|''&kappa;''}}
{{defn|{{math|''&kappa;''(''G'')}} (using the Greek letter kappa) can refer to the [[vertex connectivity]] of {{mvar|G}} or to the {{gli|clique|clique number}} of {{mvar|G}}.}}

{{term|kernel}}
{{defn|A kernel of a directed graph is a set of vertices which is both {{gli|stable}} and {{gli|absorbing}}.}}

{{term|knot}}
{{defn|An inescapable section of a {{gli|directed graph}}. See [[knot (mathematics)]] and [[knot theory]].}}

{{glossary end}}

==L==
{{glossary}}

{{term|L|''L''}}
{{defn|{{math|''L''(''G'')}} is the [[line graph]] of {{mvar|G}}; see {{gli|line}}.}}

{{term|label}}
{{defn|no=1|Information associated with a vertex or edge of a graph. A labeled graph is a graph whose vertices or edges have labels. The terms ''vertex-labeled'' or ''edge-labeled'' may be used to specify which objects of a graph have labels. [[Graph labeling]] refers to several different problems of assigning labels to graphs subject to certain constraints. See also [[graph coloring]], in which the labels are interpreted as colors.}}
{{defn|no=2|In the context of [[graph enumeration]], the vertices of a graph are said to be labeled if they are all distinguishable from each other. For instance, this can be made to be true by fixing a one-to-one correspondence between the vertices and the integers from 1 to the order of the graph. When vertices are labeled, graphs that are isomorphic to each other (but with different vertex orderings) are counted as separate objects. In contrast, when the vertices are unlabeled, graphs that are isomorphic to each other are not counted separately.}}

{{term|leaf}}
{{defn|no=1|A leaf vertex or pendant vertex (especially in a tree) is a vertex whose degree is&nbsp;{{math|1}}. A leaf edge or pendant edge is the edge connecting a leaf vertex to its single neighbour.}}
{{defn|no=2|A [[leaf power]] of a tree is a graph whose vertices are the leaves of the tree and whose edges connect leaves whose distance in the tree is at most a given threshold.}}

{{term|length}}
{{defn|In an unweighted graph, the length of a cycle, path, or walk is the number of edges it uses. In a weighted graph, it may instead be the sum of the weights of the edges that it uses. Length is used to define the [[shortest path]], [[girth (graph theory)|girth]] (shortest cycle length), and [[longest path]] between two vertices in a graph.}}

{{term|level}}
{{defn|no=1|This is the ''depth'' of a node plus 1, although some<ref name="NIST Level">{{citation|url=https://xlinux.nist.gov/dads/HTML/level.html|title=level | publisher = [[NIST]]}}</ref> define it instead to be synonym of ''depth''. A node's level in a rooted tree is the number of nodes in the path from the root to the node. For instance, the root has level 1 and any one of its adjacent nodes has level 2. }}
{{defn|no=2|A set of all node having the same level or depth.<ref  name="NIST Level"/>}}

{{term|line}}
{{defn|A synonym for an undirected edge. The [[line graph]] {{math|''L''(''G'')}} of a graph {{mvar|G}} is a graph with a vertex for each edge of {{mvar|G}} and an edge for each pair of edges that share an endpoint in {{mvar|G}}.}}

{{term|linkage}}
{{defn|A synonym for {{gli|degeneracy}}.}}

{{term|list}}
{{defn|no=1|An [[adjacency list]] is a computer representation of graphs for use in graph algorithms.}}
{{defn|no=2|[[List coloring]] is a variation of graph coloring in which each vertex has a list of available colors.}}

{{term|local}}
{{defn|A local property of a graph is a property that is determined only by the [[Neighbourhood (graph theory)|neighbourhoods]] of the vertices in the graph. For instance, a graph is locally finite if all of its neighborhoods are finite.}}

{{term|loop}}
{{defn|A [[Loop (graph theory)|loop]] or self-loop is an edge both of whose endpoints are the same vertex. It forms a cycle of length {{math|1}}. These are not allowed in simple graphs.}}

{{glossary end}}

==M==
{{glossary}}

{{term|magnification}}
{{defn|Synonym for vertex {{gli|expansion}}.}}

{{term|matching}}
{{defn|A [[Matching (graph theory)|matching]] is a set of edges in which no two share any vertex. A vertex is matched or saturated if it is one of the endpoints of an edge in the matching. A [[perfect matching]] or complete matching is a matching that matches every vertex; it may also be called a 1-factor, and can only exist when the order is even. A near-perfect matching, in a graph with odd order, is one that saturates all but one vertex. A [[maximum matching]] is a matching that uses as many edges as possible; the matching number {{math|''&alpha;''′(''G'')}} of a graph {{mvar|G}} is the number of edges in a maximum matching. A [[maximal matching]] is a matching to which no additional edges can be added.}}

{{term|maximal}}
{{defn|no=1|A subgraph of given graph {{mvar|G}} is maximal for a particular property if it has that property but no other supergraph of it that is also a subgraph of {{mvar|G}} also has the same property. That is, it is a [[maximal element]] of the subgraphs with the property. For instance, a [[maximal clique]] is a complete subgraph that cannot be expanded to a larger complete subgraph. The word "maximal" should be distinguished from "maximum": a maximum subgraph is always maximal, but not necessarily vice versa.}}
{{defn|no=2|A simple graph with a given property is maximal for that property if it is not possible to add any more edges to it (keeping the vertex set unchanged) while preserving both the simplicity of the graph and the property. Thus, for instance, a [[maximal planar graph]] is a planar graph such that adding any more edges to it would create a non-planar graph.}}

{{term|maximum}}
{{defn|A subgraph of a given graph {{mvar|G}} is maximum for a particular property if it is the largest subgraph (by order or size) among all subgraphs with that property. For instance, a [[maximum clique]] is any of the largest cliques in a given graph.}}

{{term|median}}
{{defn|no=1|A median of a triple of vertices, a vertex that belongs to shortest paths between all pairs of vertices, especially in median graphs and [[modular graph]]s.}}
{{defn|no=2|A [[median graph]] is a graph in which every three vertices have a unique median.}}

{{term|Meyniel}}
{{defn|no=1|Henri Meyniel, French graph theorist.}}
{{defn|no=2|A [[Meyniel graph]] is a graph in which every odd cycle of length five or more has at least two chords.}}

{{term|minimal}}
{{defn|A subgraph of given graph is minimal for a particular property if it has that property but no proper subgraph of it also has the same property. That is, it is a [[minimal element]] of the subgraphs with the property.}}

{{term|minimum cut|[[minimum cut]]}}
{{defn|A {{gli|cut}} whose {{gli|cut-set}} has minimum total weight, possibly restricted to cuts that separate a designated pair of vertices; they are characterized by the [[max-flow min-cut theorem]].}}

{{term|minor}}
{{defn|A graph {{mvar|H}} is a [[graph minor|minor]] of another graph {{mvar|G}} if {{mvar|H}} can be obtained by deleting edges or vertices from {{mvar|G}} and contracting edges in {{mvar|G}}. It is a [[shallow minor]] if it can be formed as a minor in such a way that the subgraphs of {{mvar|G}} that were contracted to form vertices of {{mvar|H}} all have small diameter. {{mvar|H}} is a [[topological minor]] of {{mvar|G}} if {{mvar|G}} has a subgraph that is a [[Subdivision (graph theory)|subdivision]] of {{mvar|H}}. A graph is {{mvar|H}}-minor-free if it does not have {{mvar|H}} as a minor. A family of graphs is minor-closed if it is closed under minors; the [[Robertson–Seymour theorem]] characterizes minor-closed families as having a finite set of {{gli|forbidden}} minors.}}

{{term|mixed}}
{{defn|A [[mixed graph]] is a graph that may include both directed and undirected edges.}}

{{term|modular}}
{{defn|no=1|[[Modular graph]], a graph in which each triple of vertices has at least one median vertex that belongs to shortest paths between all pairs of the triple.}}
{{defn|no=2|[[Modular decomposition]], a decomposition of a graph into subgraphs within which all vertices connect to the rest of the graph in the same way.}}
{{defn|no=3|[[Modularity (networks)|Modularity]] of a graph clustering, the difference of the number of cross-cluster edges from its expected value.}}

{{term|monotone}}
{{defn|A monotone property of graphs is a property that is closed under subgraphs: if {{mvar|G}} has a monotone property, then so must every subgraph of {{mvar|G}}. Compare {{gli|hereditary}} (closed under induced subgraphs) or ''minor-closed'' (closed under minors).}}

{{term|Moore graph}}
{{defn|A [[Moore graph]] is a regular graph for which the Moore bound is met exactly. The Moore bound is an inequality relating the degree, diameter, and order of a graph, proved by [[Edward F. Moore]]. Every Moore graph is a cage.}}

{{term|multigraph}}
{{defn|A [[multigraph]] is a graph that allows multiple adjacencies (and, often, self-loops); a graph that is not required to be simple.}}

{{term|multiple adjacency}}
{{defn|A multiple adjacency or multiple edge is a set of more than one edge that all have the same endpoints (in the same direction, in the case of directed graphs). A graph with multiple edges is often called a multigraph.}}

{{term|multiplicity}}
{{defn|The multiplicity of an edge is the number of edges in a multiple adjacency. The multiplicity of a graph is the maximum multiplicity of any of its edges.}}

{{glossary end}}

==N==
{{glossary}}

{{term|N|''N''}}
{{defn|no=1|For the notation for open and closed neighborhoods, see {{gli|neighbourhood}}.}}
{{defn|no=2|A lower-case {{mvar|n}} is often used (especially in computer science) to denote the number of vertices in a given graph.}}

{{term|neighbor}}
{{term|neighbour|multi=y}}
{{defn|A vertex that is adjacent to a given vertex.}}

{{term|neighborhood}}
{{term|neighbourhood|multi=y}}
{{defn|The [[neighbourhood (graph theory)|open neighbourhood]] (or neighborhood) of a vertex {{mvar|v}} is the subgraph induced by all vertices that are adjacent to {{mvar|v}}. The closed neighbourhood is defined in the same way but also includes {{mvar|v}} itself. The open neighborhood of {{mvar|v}} in {{mvar|G}} may be denoted {{math|''N''<sub>''G''</sub>(''v'')}} or {{math|''N''(''v'')}}, and the closed neighborhood may be denoted {{math|''N''<sub>''G''</sub>[''v'']}} or {{math|''N''[''v'']}}. When the openness or closedness of a neighborhood is not specified, it is assumed to be open.}}

{{term|network}}
{{defn|A graph in which attributes (e.g. names) are associated with the nodes and/or edges.}}

{{term|node}}
{{defn|A synonym for {{gli|vertex}}.}}

{{term|non-edge}}
{{defn|A non-edge or anti-edge is a pair of vertices that are not adjacent; the edges of the complement graph.}}

{{term|null graph}}
{{defn|See {{gli|empty graph}}.}}

{{glossary end}}

==O==
{{glossary}}

{{term|odd}}
{{defn|no=1|An odd cycle is a cycle whose length is odd. The [[Girth (graph theory)|odd girth]] of a non-bipartite graph is the length of its shortest odd cycle. An odd hole is a special case of an odd cycle: one that is induced and has four or more vertices.}}
{{defn|no=2|An odd vertex is a vertex whose degree is odd. By the [[handshaking lemma]] every finite undirected graph has an even number of odd vertices.}}
{{defn|no=3|An odd ear is a simple path or simple cycle with an odd number of edges, used in odd ear decompositions of factor-critical graphs; see {{gli|ear}}.}}
{{defn|no=4|An odd chord is an edge connecting two vertices that are an odd distance apart in an even cycle. Odd chords are used to define [[strongly chordal graph]]s.}}
{{defn|no=5|An [[odd graph]] is a special case of a [[Kneser graph]], having one vertex for each {{math|(''n'' &minus; 1)}}-element subset of a {{math|(2''n'' &minus; 1)}}-element set, and an edge connecting two subsets when their corresponding sets are disjoint.}}

{{term|open}}
{{defn|no=1|See {{gli|neighbourhood}}.}}
{{defn|no=2|See {{gli|walk}}.}}

{{term|order|content ={{vanchor|order}} }}
{{defn|no=1|The order of a graph {{mvar|G}} is the number of its vertices, {{math|{{!}}''V''(''G''){{!}}}}. The variable {{mvar|n}} is often used for this quantity. See also {{gli|size}}, the number of edges.}}
{{defn|no=2|A type of [[logic of graphs]]; see {{gli|first order}} and {{gli|second order}}.}}
{{defn|no=3|An order or ordering of a graph is an arrangement of its vertices into a sequence, especially in the context of [[topological ordering]] (an order of a directed acyclic graph in which every edge goes from an earlier vertex to a later vertex in the order) and [[degeneracy (graph theory)|degeneracy ordering]] (an order in which each vertex has minimum degree in the induced subgraph of it and all later vertices).}}
{{defn|no=4|For the order of a haven or bramble, see {{gli|haven}} and {{gli|bramble}}.}}

{{term|orientation}}
{{term|oriented|multi=y}}
{{defn|no=1|An [[Orientation (graph theory)|orientation]] of an undirected graph is an assignment of directions to its edges, making it into a directed graph. An oriented graph is one that has been assigned an orientation. So, for instance, a [[polytree]] is an oriented tree; it differs from a directed tree (an arborescence) in that there is no requirement of consistency in the directions of its edges. Other special types of orientation include [[Tournament (graph theory)|tournaments]], orientations of complete graphs; [[strong orientation]]s, orientations that are strongly connected; [[acyclic orientation]]s, orientations that are acyclic; [[Eulerian path|Eulerian orientation]]s, orientations that are Eulerian; and [[transitive orientation]]s, orientations that are transitively closed.}}
{{defn|no=2|Oriented graph, used by some authors as a synonym for a [[directed graph]].}}

{{term|out-degree}}
{{defn|See {{gli|degree}}.}}

{{term|outer}}
{{defn|See {{gli|face}}.}}

{{term|outerplanar}}
{{defn|An [[outerplanar graph]] is a graph that can be embedded in the plane (without crossings) so that all vertices are on the outer face of the graph.}}

{{glossary end}}

==P==
{{glossary}}

{{term|parent}}
{{defn|In a rooted tree, a parent of a vertex {{mvar|v}} is a neighbor of {{mvar|v}} along the incoming edge, the one that is directed toward the root.}}

{{term|path}}
{{defn|A [[Path (graph theory)|path]] may either be a walk or a walk without repeated vertices and consequently edges (also called a simple path), depending on the source. Important special cases include [[induced path]]s and [[shortest path]]s.}}

{{term|path decomposition}}
{{defn|A [[path decomposition]] of a graph {{mvar|G}} is a tree decomposition whose underlying tree is a path. Its width is defined in the same way as for tree decompositions, as one less than the size of the largest bag. The minimum width of any path decomposition of {{mvar|G}} is the pathwidth of {{mvar|G}}.}}

{{term|pathwidth}}
{{defn|The [[pathwidth]] of a graph {{mvar|G}} is the minimum width of a path decomposition of {{mvar|G}}. It may also be defined in terms of the clique number of an interval completion of {{mvar|G}}. It is always between the bandwidth and the treewidth of {{mvar|G}}. It is also known as interval thickness, vertex separation number, or node searching number.}}

{{term|pendant}}
{{defn|See {{gli|leaf}}.}}

{{term|perfect}}
{{defn|no=1|A [[perfect graph]] is a graph in which, in every induced subgraph, the chromatic number equals the clique number. The [[perfect graph theorem]] and [[strong perfect graph theorem]] are two theorems about perfect graphs, the former proving that their complements are also perfect and the latter proving that they are exactly the graphs with no odd holes or anti-holes.}}
{{defn|no=2|A [[perfectly orderable graph]] is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with this ordering optimally colors every induced subgraph. The perfectly orderable graphs are a subclass of the perfect graphs.}}
{{defn|no=3|A [[perfect matching]] is a matching that saturates every vertex; see {{gli|matching}}.}}
{{defn|no=4|A perfect [[1-factorization]] is a partition of the edges of a graph into perfect matchings so that each two matchings form a Hamiltonian cycle.}}

{{term|peripheral}}
{{defn|no=1|A [[peripheral cycle]] or non-separating cycle is a cycle with at most one bridge.}}
{{anchor|peripheral vertex}}{{defn|no=2|A peripheral vertex is a vertex whose {{gli|eccentricity}} is maximum. In a tree, this must be a leaf.}}

{{term|Petersen}}
{{defn|no=1|[[Julius Petersen]] (1839–1910), Danish graph theorist.}}
{{defn|no=2|The [[Petersen graph]], a 10-vertex 15-edge graph frequently used as a counterexample.}}
{{defn|no=3|[[Petersen's theorem]] that every bridgeless cubic graph has a perfect matching.}}

{{term|planar}}
{{defn|A [[planar graph]] is a graph that has an [[graph embedding|embedding]] onto the Euclidean plane. A plane graph is a planar graph for which a particular embedding has already been fixed. A {{mvar|k}}-planar graph is one that can be drawn in the plane with at most {{mvar|k}} crossings per edge.}}

{{term|polytree}}
{{defn|A [[polytree]] is an oriented tree; equivalently, a directed acyclic graph whose underlying undirected graph is a tree.}}

{{term|power}}
{{defn|no=1|A [[graph power]] {{math|''G''<sup>''k''</sup>}} of a graph {{mvar|G}} is another graph on the same vertex set; two vertices are adjacent in {{math|''G''<sup>''k''</sup>}} when they are at distance at most {{mvar|k}} in {{mvar|G}}. A [[leaf power]] is a closely related concept, derived from a power of a tree by taking the subgraph induced by the tree's leaves.}}
{{defn|no=2|[[Power graph analysis]] is a method for analyzing complex networks by identifying cliques, bicliques, and stars within the network.}}
{{defn|no=3|[[Power law]]s in the [[degree distribution]]s of [[scale-free network]]s are a phenomenon in which the number of vertices of a given degree is proportional to a power of the degree.}}

{{term|predecessor}}
{{defn|A {{gli|vertex}} coming before a given vertex in a {{gli|directed path}}.}}

{{term|prime}}
{{defn|no=1|A [[prime graph]] is defined from an algebraic [[group (mathematics)|group]], with a vertex for each [[prime number]] that divides the order of the group.}}
{{defn|no=2|In the theory of [[modular decomposition]], a prime graph is a graph without any nontrivial modules.}}
{{defn|no=3|In the theory of [[Split (graph theory)|splits]], cuts whose cut-set is a complete bipartite graph, a prime graph is a graph without any splits. Every quotient graph of a maximal decomposition by splits is a prime graph, a star, or a complete graph.}}
{{defn|no=4|A prime graph for the [[Cartesian product of graphs]] is a connected graph that is not itself a product. Every connected graph can be uniquely factored into a Cartesian product of prime graphs.}}

{{term|proper}}
{{defn|no=1|A proper subgraph is a subgraph that removes at least one vertex or edge relative to the whole graph; for finite graphs, proper subgraphs are never isomorphic to the whole graph, but for infinite graphs they can be.}}
{{defn|no=2|A proper coloring is an assignment of colors to the vertices of a graph (a coloring) that assigns different colors to the endpoints of each edge; see {{gli|color}}.}}
{{defn|no=3|A [[proper interval graph]] or proper circular arc graph is an intersection graph of a collection of intervals or circular arcs (respectively) such that no interval or arc contains another interval or arc. Proper interval graphs are also called unit interval graphs (because they can always be represented by unit intervals) or indifference graphs.}}

{{term|property}}
{{defn|A [[graph property]] is something that can be true of some graphs and false of others, and that depends only on the graph structure and not on incidental information such as labels. Graph properties may equivalently be described in terms of classes of graphs (the graphs that have a given property). More generally, a graph property may also be a function of graphs that is again independent of incidental information, such as the size, order, or degree sequence of a graph; this more general definition of a property is also called an invariant of the graph.}}

{{term|pseudoforest}}
{{defn|A [[pseudoforest]] is an undirected graph in which each connected component has at most one cycle, or a directed graph in which each vertex has at most one outgoing edge.}}

{{term|pseudograph}}
{{defn|A pseudograph is a graph or multigraph that allows self-loops.}}

{{glossary end}}

==Q==
{{glossary}}

{{term|quasi-line graph}}
{{defn|A quasi-line graph or locally co-bipartite graph is a graph in which the open neighborhood of every vertex can be partitioned into two cliques. These graphs are always [[claw-free graph|claw-free]] and they include as a special case the [[line graph]]s. They are used in the structure theory of claw-free graphs.}}

{{term|quasi-random graph sequence}}
{{defn|A [[quasi-random graph|quasi-random graph sequence]] is a sequence of graphs that shares several properties with a sequence of [[random graphs]] generated according to the [[Erdős–Rényi model|Erdős–Rényi random graph model]].}}

{{term|quiver}}
{{defn|A [[Quiver (mathematics)|quiver]] is a directed multigraph, as used in [[category theory]]. The edges of a quiver are called arrows.}}

{{glossary end}}

==R==
{{glossary}}

{{term|radius}}
{{defn|The radius of a graph is the minimum {{gli|eccentricity}} of any vertex.}}

{{term|Ramanujan}}
{{defn|A [[Ramanujan graph]] is a graph whose spectral expansion is as large as possible. That is, it is a {{mvar|d}}-regular graph, such that the second-largest eigenvalue of its adjacency matrix is at most <math>2\sqrt{d-1}</math>.}}

{{term|ray}}
{{defn|A ray, in an infinite graph, is an infinite simple path with exactly one endpoint. The [[End (graph theory)|ends]] of a graph are equivalence classes of rays.}}

{{term|reachability|[[reachability]]}}
{{defn|The ability to get from one {{gli|vertex}} to another within a {{gli|graph}}.}}

{{term|reachable}}
{{defn|Has an affirmative {{gli|reachability}}. A {{gli|vertex}} {{math|''y''}} is said to be reachable from a vertex {{math|''x''}} if there exists a {{gli|path}} from {{math|''x''}} to {{math|''y''}}.}}

{{term|recognizable}}
{{defn|In the context of the [[reconstruction conjecture]], a graph property is recognizable if its truth can be determined from the deck of the graph. Many graph properties are known to be recognizable. If the reconstruction conjecture is true, all graph properties are recognizable.}}

{{term|reconstruction}}
{{defn|The [[reconstruction conjecture]] states that each undirected graph {{mvar|G}} is uniquely determined by its ''deck'', a multiset of graphs formed by removing one vertex from {{mvar|G}} in all possible ways. In this context, reconstruction is the formation of a graph from its deck.}}

{{term|rectangle}}
{{defn|A simple cycle consisting of exactly four edges and four vertices.}}

{{term|regular}}
{{defn|A graph is {{mvar|d}}-regular when all of its vertices have degree {{mvar|d}}. A [[regular graph]] is a graph that is {{mvar|d}}-regular for some {{mvar|d}}.}}

{{term|regular tournament}}
{{defn|A regular tournament is a tournament where in-degree equals out-degree for all vertices.}}

{{term|reverse}}
{{defn|See {{gli|transpose}}.}}

{{term|root}}
{{defn|no=1|A designated vertex in a graph, particularly in directed trees and [[rooted graph]]s.}}
{{defn|no=2|The inverse operation to a [[graph power]]: a {{mvar|k}}th root of a graph {{mvar|G}} is another graph on the same vertex set such that two vertices are adjacent in {{mvar|G}} if and only if they have distance at most {{mvar|k}} in the root.}}

{{glossary end}}

==S==
{{glossary}}

{{term|saturated}}
{{defn|See {{gli|matching}}.}}

{{term|searching number}}
{{defn|Node searching number is a synonym for {{gli|pathwidth}}.}}

{{term|second order}}
{{defn|The second order [[logic of graphs]] is a form of logic in which variables may represent vertices, edges, sets of vertices, and (sometimes) sets of edges. This logic includes predicates for testing whether a vertex and edge are incident, as well as whether a vertex or edge belongs to a set. To be distinguished from first order logic, in which variables can only represent vertices.}}

{{term|self-loop}}
{{defn|Synonym for {{gli|loop}}.}}

{{term|separating vertex}}
{{defn|See {{gli|articulation point}}.}}

{{term|separation number}}
{{defn|Vertex separation number is a synonym for {{gli|pathwidth}}.}}

{{term|sibling}}
{{defn|In a rooted tree, a sibling of a vertex {{mvar|v}} is a vertex which has the same parent vertex as  {{mvar|v}}.}}

{{anchor|simple graph}}{{term|simple}}
{{defn|no=1|A [[simple graph]] is a graph without loops and without multiple adjacencies. That is, each edge connects two distinct endpoints and no two edges have the same endpoints. A simple edge is an edge that is not part of a multiple adjacency. In many cases, graphs are assumed to be simple unless specified otherwise.}}
{{defn|no=2|A simple path or a simple cycle is a path or cycle that has no repeated vertices and consequently no repeated edges.}}

{{term|sink}}
{{defn|A sink, in a directed graph, is a vertex with no outgoing edges (out-degree equals 0).}}

{{term|size}}
{{defn|The size of a graph {{mvar|G}} is the number of its edges, {{math|{{!}}''E''(''G''){{!}}}}.<ref>{{citation|last=Harris|first=John M.|title=Combinatorics and Graph Theory|year=2000|publisher=Springer-Verlag|location=New York|isbn=978-0-387-98736-1|page=5|url=https://www.springer.com/gp/book/9780387797106}}</ref> The variable {{mvar|m}} is often used for this quantity. See also ''order'', the number of vertices.}}

{{term|small-world network}}
{{defn|A [[small-world network]] is a graph in which most nodes are not neighbors of one another, but most nodes can be reached from every other node by a small number of hops or steps.  Specifically, a small-world network is defined to be a graph where the typical distance ''L'' between two randomly chosen nodes (the number of steps required) grows proportionally to the logarithm of the number of nodes ''N'' in the network<ref>{{citation|title=Collective dynamics of 'small-world' networks|first1=Duncan J.|last1=Watts|first2=Steven H.|last2=Strogatz|date=June 1998|journal=Nature|volume=393|issue=6684|pages=440–442|doi=10.1038/30918|bibcode=1998Natur.393..440W|pmid=9623998|s2cid=4429113}}</ref>}}

{{term|snark}}
{{defn|A [[Snark (graph theory)|snark]] is a simple, connected, bridgeless cubic graph with chromatic index equal to 4.}}

{{term|source}}
{{defn|A source, in a directed graph, is a vertex with no incoming edges (in-degree equals 0).}}

{{term|space}}
{{defn|In [[algebraic graph theory]], several [[vector spaces]] over the [[GF(2)|binary field]] may be associated with a graph. Each has sets of edges or vertices for its vectors, and [[symmetric difference]] of sets as its vector sum operation. The [[edge space]] is the space of all sets of edges, and the [[vertex space]] is the space of all sets of vertices. The [[cut space]] is a subspace of the edge space that has the cut-sets of the graph as its elements. The [[cycle space]] has the Eulerian spanning subgraphs as its elements.}}

{{term|spanner}}
{{defn|A spanner is a (usually sparse) graph whose shortest path distances approximate those in a dense graph or other metric space. Variations include [[geometric spanner]]s, graphs whose vertices are points in a geometric space; [[tree spanner]]s, spanning trees of a graph whose distances approximate the graph distances, and graph spanners, sparse subgraphs of a dense graph whose distances approximate the original graph's distances. A greedy spanner is a graph spanner constructed by a greedy algorithm, generally one that considers all edges from shortest to longest and keeps the ones that are needed to preserve the distance approximation.}}

{{term|spanning}}
{{defn|A subgraph is spanning when it includes all of the vertices of the given graph.
Important cases include [[spanning tree]]s, spanning subgraphs that are trees, and [[perfect matching]]s, spanning subgraphs that are matchings. A spanning subgraph may also be called a [[Graph factorization|factor]], especially (but not only) when it is regular.}}

{{term|sparse}}
{{defn|A [[sparse graph]] is one that has few edges relative to its number of vertices. In some definitions the same property should also be true for all subgraphs of the given graph.}}

{{term|spectral}}
{{term|spectrum|multi=y}}
{{defn|The spectrum of a graph is the collection of [[eigenvalue]]s of its adjacency matrix. [[Spectral graph theory]] is the branch of graph theory that uses spectra to analyze graphs. See also spectral {{gli|expansion}}.}}

{{term|split}}
{{defn|no=1|A [[split graph]] is a graph whose vertices can be partitioned into a clique and an independent set. A related class of graphs, the double split graphs, are used in the proof of the strong perfect graph theorem.}}
{{defn|no=2|A [[split (graph theory)|split]] of an arbitrary graph is a partition of its vertices into two nonempty subsets, such that the edges spanning this cut form a complete bipartite subgraph. The splits of a graph can be represented by a tree structure called its ''split decomposition''. A split is called a strong split when it is not crossed by any other split. A split is called nontrivial when both of its sides have more than one vertex. A graph is called prime when it has no nontrivial splits.}}
{{defn|no=3|[[Edge contraction#Vertex cleaving|Vertex splitting]] (sometimes called vertex cleaving) is an elementary graph operation that splits a vertex into two, where these two new vertices are adjacent to the vertices that the original vertex was adjacent to. The inverse of  vertex splitting is vertex contraction.}}

{{term|square}}
{{defn|no=1|The square of a graph {{mvar|G}} is the [[graph power]] {{math|''G''<sup>2</sup>}}; in the other direction, {{mvar|G}} is the square root of {{math|''G''<sup>2</sup>}}. The [[half-square]] of a bipartite graph is the subgraph of its square induced by one side of the bipartition.}}
{{defn|no=2|A [[squaregraph]] is a planar graph that can be drawn so that all bounded faces are 4-cycles and all vertices of degree ≤ 3 belong to the outer face.}}
{{defn|no=3|A square grid graph is a [[lattice graph]] defined from points in the plane with integer coordinates connected by unit-length edges.}}

{{term|stable}}
{{defn|A stable set is a synonym for an {{gli|independent|independent set}}.}}

{{term|star}}
{{defn|A [[Star (graph theory)|star]] is a tree with one internal vertex; equivalently, it is a complete bipartite graph {{math|''K''<sub>1,''n''</sub>}} for some {{math|''n'' ≥ 2}}. The special case of a star with three leaves is called a claw.}}

{{term|strength}}
{{defn|The [[strength of a graph]] is the minimum ratio of the number of edges removed from the graph to components created, over all possible removals; it is analogous to toughness, based on vertex removals.}}

{{term|strong}}
{{defn|no=1|For strong connectivity and [[strongly connected component]]s of directed graphs, see {{gli|connected}} and {{gli|component}}. A [[strong orientation]] is an orientation that is strongly connected; see {{gli|orientation}}.}}
{{defn|no=2|For the [[strong perfect graph theorem]], see {{gli|perfect}}.}}
{{defn|no=3|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.}}
{{defn|no=4|A [[strongly chordal graph]] is a chordal graph in which every even cycle of length six or more has an odd chord.}}
{{defn|no=5|A strongly perfect graph is a graph in which every induced subgraph has an independent set meeting all maximal cliques. The [[Meyniel graph]]s are also called "very strongly perfect graphs" because in them, every vertex belongs to such an independent set.}}

{{term|subforest}}
{{defn|A subgraph of a {{gli|forest}}.}}

{{term|subgraph}}
{{defn|A subgraph of a graph {{mvar|G}} is another graph formed from a subset of the vertices and edges of {{mvar|G}}. The vertex subset must include all endpoints of the edge subset, but may also include additional vertices. A spanning subgraph is one that includes all vertices of the graph; an induced subgraph is one that includes all the edges whose endpoints belong to the vertex subset.}}

{{term|subtree}}
{{defn|A subtree is a connected subgraph of a tree. Sometimes, for rooted trees, subtrees are defined to be a special type of connected subgraph, formed by all vertices and edges reachable from a chosen vertex.}}

{{term|successor}}
{{defn|A {{gli|vertex}} coming after a given vertex in a {{gli|directed path}}.}}

{{term|superconcentrator}}
{{defn|A superconcentrator is a graph with two designated and equal-sized subsets of vertices {{mvar|I}} and {{mvar|O}}, such that for every two equal-sized subsets {{mvar|S}} of {{mvar|I}} and {{mvar|T}} of {{mvar|O}} there exists a family of disjoint paths connecting every vertex in {{mvar|S}} to a vertex in {{mvar|T}}. Some sources require in addition that a superconcentrator be a directed acyclic graph, with {{mvar|I}} as its sources and {{mvar|O}} as its sinks.}}

{{term|supergraph}}
{{defn|A graph formed by adding vertices, edges, or both to a given graph. If {{mvar|H}} is a subgraph of {{mvar|G}}, then {{mvar|G}} is a supergraph of {{mvar|H}}.}}

{{glossary end}}

==T==
{{glossary}}

{{term|theta}}
{{defn|no=1|A theta graph is the union of three internally disjoint (simple) paths that have the same two distinct end vertices.<ref>{{citation
 | last = Bondy | first = J. A.
 | contribution = The "graph theory" of the Greek alphabet
 | doi = 10.1007/BFb0067356
 | mr = 0335362
 | pages = 43–54
 | publisher = Springer
 | series = Lecture Notes in Mathematics
 | title = Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs)
 | volume = 303
 | year = 1972| isbn = 978-3-540-06096-3
 }}</ref>}}
{{defn|no=2|The [[theta graph]] of a collection of points in the Euclidean plane is constructed by constructing a system of cones surrounding each point and adding one edge per cone, to the point whose projection onto a central ray of the cone is smallest.}}
{{defn|no=3|The [[Lovász number]] or Lovász theta function of a graph is a graph invariant related to the clique number and chromatic number that can be computed in polynomial time by semidefinite programming.}}

{{term|Thomsen graph}}
{{defn|The [[Thomsen graph]] is a name for the [[complete bipartite graph]] <math>K_{3,3}</math>.}}

{{term|topological}}
{{defn|no=1|A [[topological graph]] is a representation of the vertices and edges of a graph by points and curves in the plane (not necessarily avoiding crossings).}}
{{defn|no=2|[[Topological graph theory]] is the study of graph embeddings.}}
{{defn|no=3|[[Topological sorting]] is the algorithmic problem of arranging a directed acyclic graph into a topological order, a vertex sequence such that each edge goes from an earlier vertex to a later vertex in the sequence.}}

{{term|totally disconnected}}
{{defn|Synonym for {{gli|edgeless graph|edgeless}}.}}

{{term|tour}}
{{defn|A closed trail, a {{gli|walk}} that starts and ends at the same vertex and has no repeated edges. Euler tours are tours that use all of the graph edges; see {{gli|Eulerian}}.}}

{{term|tournament}}
{{defn|A [[Tournament (graph theory)|tournament]] is an orientation of a complete graph; that is, it is a directed graph such that every two vertices are connected by exactly one directed edge (going in only one of the two directions between the two vertices).}}

{{term|traceable}}
{{defn|A [[traceable graph]] is a graph that contains a Hamiltonian path.}}

{{term|trail}}
{{defn|A {{gli|walk}} without repeated edges.}}

{{term|transitive}}
{{defn|Having to do with the [[transitive property]]. The [[transitive closure]] of a given directed graph is a graph on the same vertex set that has an edge from one vertex to another whenever the original graph has a path connecting the same two vertices. A [[transitive reduction]] of a graph is a minimal graph having the same transitive closure; directed acyclic graphs have a unique transitive reduction. A [[transitive orientation]] is an orientation of a graph that is its own transitive closure; it exists only for [[comparability graph]]s.}}

{{term|transpose}}
{{defn|The [[transpose graph]] of a given directed graph is a graph on the same vertices, with each edge reversed in direction. It may also be called the converse or reverse of the graph.}}

{{term|tree}}
{{defn|no=1|A [[Tree (graph theory)|tree]] is an undirected graph that is both connected and acyclic, or a directed graph in which there exists a unique walk from one vertex (the root of the tree) to all remaining vertices.}}
{{defn|no=2|A [[k-tree|{{mvar|k}}-tree]] is a graph formed by gluing {{math|(''k'' + 1)}}-cliques together on shared {{mvar|k}}-cliques. A tree in the ordinary sense is a {{math|1}}-tree according to this definition.}}

{{term|tree decomposition}}
{{defn|A [[tree decomposition]] of a graph {{mvar|G}} is a tree whose nodes are labeled with sets of vertices of {{mvar|G}}; these sets are called bags. For each vertex {{mvar|v}}, the bags that contain {{mvar|v}} must induce a subtree of the tree, and for each edge {{mvar|uv}} there must exist a bag that contains both {{mvar|u}} and {{mvar|v}}. The width of a tree decomposition is one less than the maximum number of vertices in any of its bags; the treewidth of {{mvar|G}} is the minimum width of any tree decomposition of {{mvar|G}}.}}

{{term|treewidth}}
{{defn|The [[treewidth]] of a graph {{mvar|G}} is the minimum width of a tree decomposition of {{mvar|G}}. It can also be defined in terms of the clique number of a [[chordal completion]] of {{mvar|G}}, the order of a [[Haven (graph theory)|haven]] of {{mvar|G}}, or the order of a [[Bramble (graph theory)|bramble]] of {{mvar|G}}.}}

{{term|triangle}}
{{defn|A cycle of length three in a graph. A [[triangle-free graph]] is an undirected graph that does not have any triangle subgraphs.}}

{{term|trivial}}
{{defn|A trivial graph is a graph with 0 or 1 vertices.<ref>{{citation |last=Diestel |first=Reinhard |url=http://link.springer.com/10.1007/978-3-662-53622-3 |title=Graph Theory |date=2017 |publisher=Springer Berlin Heidelberg |isbn=978-3-662-53621-6 |series=Graduate Texts in Mathematics |volume=173 |location=Berlin, Heidelberg |language=en |doi=10.1007/978-3-662-53622-3 |page=2}}</ref> A graph with 0 vertices is also called [[null graph]].}}

{{term|Turán}}
{{defn|no=1|[[Pál Turán]]}}
{{defn|no=2|A [[Turán graph]] is a balanced complete multipartite graph.}}
{{defn|no=3|[[Turán's theorem]] states that Turán graphs have the maximum number of edges among all clique-free graphs of a given order.}}
{{defn|no=4|[[Turán's brick factory problem]] asks for the minimum number of crossings in a drawing of a complete bipartite graph.}}

{{term|twin}}
{{defn|Two vertices {{mvar|u,v}} are true twins if they have the same closed {{gli|neighborhood}}: {{math|''N''{{sub|''G''}}[''u''] {{=}} ''N''{{sub|''G''}}[''v'']}} (this implies {{mvar|u}} and {{mvar|v}} are neighbors), and they are false twins if they have the same open neighborhood: {{math|''N''{{sub|''G''}}(''u'') {{=}} ''N''{{sub|''G''}}(''v''))}} (this implies {{mvar|u}} and {{mvar|v}} are not neighbors).}}

{{glossary end}}

==U==
{{glossary}}

{{term|unary vertex}}
{{defn|In a rooted tree, a unary vertex is a vertex which has exactly one child vertex.}}

{{term|undirected}}
{{defn|An [[undirected graph]] is a graph in which the two endpoints of each edge are not distinguished from each other. See also ''directed'' and ''mixed''. In a [[mixed graph]], an undirected edge is again one in which the endpoints are not distinguished from each other.}}

{{term|uniform}}
{{defn|A hypergraph is {{mvar|k}}-uniform when all its edges have {{mvar|k}} endpoints, and uniform when it is {{mvar|k}}-uniform for some {{mvar|k}}. For instance, ordinary graphs are the same as {{math|2}}-uniform hypergraphs.}}

{{term|universal}}
{{defn|no=1|A [[universal graph]] is a graph that contains as subgraphs all graphs in a given family of graphs, or all graphs of a given size or order within a given family of graphs.}}
{{defn|no=2|A [[universal vertex]] (also called an apex or dominating vertex) is a vertex that is adjacent to every other vertex in the graph. For instance, [[wheel graph]]s and connected [[threshold graph]]s always have a universal vertex.}}
{{defn|no=3|In the [[logic of graphs]], a vertex that is [[universal quantifier|universally quantified]] in a formula may be called a universal vertex for that formula.}}

{{term|unweighted graph}}
{{defn|A {{gli|graph}} whose {{gli|vertex|vertices}} and {{gli|edge}}s have not been assigned {{gli|weight}}s; the opposite of a {{gli|weighted graph}}.}}

{{term|utility graph}}
{{defn|The [[utility graph]] is a name for the [[complete bipartite graph]] <math>K_{3,3}</math>.}}

{{glossary end}}

==V==
{{glossary}}

{{term|V|''V''}}
{{defn|See ''vertex set''.}}

{{term|valency}}
{{defn|Synonym for ''{{gli|degree}}''.}}

{{term|vertex}}
{{defn|A [[Vertex (graph theory)|vertex]] (plural vertices) is (together with edges) one of the two basic units out of which graphs are constructed. Vertices of graphs are often considered to be atomic objects, with no internal structure.}}

{{term|vertex cut}}
{{term|separating set|multi=y}}
{{defn|A set of {{gli|vertex|vertices}} whose removal {{gli|disconnected|disconnects}} the {{gli|graph}}. A one-vertex cut is called an {{gli|articulation point}} or {{gli|cut vertex}}.}}

{{term|vertex set}}
{{defn|The set of vertices of a given graph {{mvar|G}}, sometimes denoted by {{math|''V''(''G'')}}.}}

{{term|vertices}}
{{defn|See ''vertex''.}}

{{term|Vizing}}
{{defn|no=1|[[Vadim G. Vizing]]}}
{{defn|no=2|[[Vizing's theorem]] that the chromatic index is at most one more than the maximum degree.}}
{{defn|no=3|[[Vizing's conjecture]] on the domination number of Cartesian products of graphs.}}

{{term|volume}}
{{defn|The sum of the degrees of a set of vertices.}}

{{glossary end}}

==W==
{{glossary}}

{{term|W|{{mvar|W}}}}
{{defn|The letter {{mvar|W}} is used in notation for [[wheel graph]]s and [[windmill graph]]s. The notation is not standardized.}}

{{term|Wagner}}
{{defn|no=1|[[Klaus Wagner]]}}
{{defn|no=2|The [[Wagner graph]], an eight-vertex Möbius ladder.}}
{{defn|no=3|[[Wagner's theorem]] characterizing planar graphs by their forbidden minors.}}
{{defn|no=4|Wagner's theorem characterizing the {{math|''K''<sub>5</sub>}}-minor-free graphs.}}

{{term|walk}}
{{defn|A [[Path (graph theory)#Walk, trail, path|walk]] is a finite or infinite [[sequence]] of [[Edge (graph theory)|edges]] which joins a sequence of [[Vertex (graph theory)|vertices]]. Walks are also sometimes called ''chains''.<ref>{{citation|url=https://www.britannica.com/topic/chain-graph-theory|title=Chain - graph theory|website=britannica.com|access-date=25 March 2018}}</ref> A walk is ''open'' if its first and last vertices are distinct, and ''closed'' if they are repeated.}}

{{term|weakly connected}}
{{defn|A {{gli|directed}} graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.}}

{{term|weight}}
{{defn|A numerical value, assigned as a label to a vertex or edge of a graph. The weight of a subgraph is the sum of the weights of the vertices or edges within that subgraph.}}

{{term|weighted graph}}
{{defn|A {{gli|graph}} whose {{gli|vertex|vertices}} or {{gli|edge}}s have been assigned {{gli|weight}}s.  A vertex-weighted graph has weights on its vertices and an edge-weighted graph has weights on its edges.}}

{{term|well-colored}}
{{defn|A [[Grundy number|well-colored graph]] is a graph all of whose [[greedy coloring]]s use the same number of colors.}}

{{term|well-covered}}
{{defn|A [[well-covered graph]] is a graph all of whose maximal independent sets are the same size.}}

{{term|wheel}}
{{defn|A [[wheel graph]] is a graph formed by adding a [[universal vertex]] to a simple cycle.}}

{{term|width}}
{{defn|no=1|A synonym for {{gli|degeneracy}}.}}
{{defn|no=2|For other graph invariants known as width, see {{gli|bandwidth}}, {{gli|branchwidth}}, {{gli|clique-width}}, {{gli|pathwidth}}, and {{gli|treewidth}}.}}
{{defn|no=3|The width of a tree decomposition or path decomposition is one less than the maximum size of one of its bags, and may be used to define treewidth and pathwidth.}}
{{defn|no=4|The width of a [[directed acyclic graph]] is the maximum cardinality of an antichain.}}

{{term|windmill}}
{{defn|A [[windmill graph]] is the union of a collection of cliques, all of the same order as each other, with one shared vertex belonging to all the cliques and all other vertices and edges distinct.}}

{{glossary end}}

==See also==
{{Portal|Mathematics}}
* [[List of graph theory topics]]
* [[Gallery of named graphs]]
* [[Graph algorithms]]
* [[Glossary of areas of mathematics]]

==References==
{{reflist|30em}}

{{wiktionary|Appendix:Glossary of graph theory}}

[[Category:Graph theory|*]]
[[Category:Glossaries of mathematics|Graph theory]]
[[Category:Wikipedia glossaries using description lists]]

[[he:גרף (תורת הגרפים)#תת גרף]]