 # Graph theory

## Graph theory Topics

Sort by:

### Walk

A walk is a sequence , , , ..., of graph vertices and graph edges such that for , the edge has endpoints and (West 2000, p. 20). The length of a walk is its number of edges.A -walk is a walk with first vertex and last vertex , where and are known as the endpoints. Every -walk contains a -graph path (West 2000, p. 21).A walk is said to be closed if its endpoints are the same. The number of (undirected) closed -walks in a graph with adjacency matrix is given by , where denotes the matrix trace. In order to compute the number of -cycles, all closed -walks that are not cycles must be subtracted. Similarly, to compute the number of graph paths, all -walks that are not graph paths (because they contain redundant vertices) must be subtracted (cf. Festinger 1949, Ross and Harary 1952).For a simple graph (which has no multiple edges),a walk may be specified completely by an ordered list of vertices (West 2000, p. 20).A trail is a walk with no repeated edges...

### K&ouml;nigsberg bridge problem

The Königsberg bridge problem asks if the seven bridges of the city of Königsberg (left figure; Kraitchik 1942), formerly in Germany but now known as Kaliningrad and part of Russia, over the river Preger can all be traversed in a single trip without doubling back, with the additional requirement that the trip ends in the same place it began. This is equivalent to asking if the multigraph on four nodes and seven edges (right figure) has an Eulerian cycle. This problem was answered in the negative by Euler (1736), and represented the beginning of graph theory.On a practical note, J. Kåhre observes that bridges and no longer exist and that and are now a single bridge passing above with a stairway in the middle leading down to . Even so, there is still no Eulerian cycle on the nodes , , , and using the modern Königsberg bridges, although there is an Eulerian path (right figure). An example Eulerian path is illustrated in the right..

### Unicursal circuit

A circuit in which an entire graph is traversed in one route. Examples of curves that can be traced unicursally are the Mohammed sign and unicursal hexagram.The numbers of distinct unicursal polygrams that can be formed from points on circle with no two adjacent for , 2, ... are 1, 0, 0, 0, 1, 3, 23, 177, 1553, ... (OEIS A002816). For , these are given by the sumThis sequence is also given by the recurrence equation

### Knight graph

The knight graph is a graph on vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a knight (which may only make moves which simultaneously shift one square along one axis and two along the other).The number of edges in the knight graph is (8 times the triangular numbers), so for , 2, ..., the first few values are 0, 0, 8, 24, 48, 80, 120, ... (OEIS A033996).Knight graphs are bipartite and therefore areperfect.The following table summarizes some named graph complements of knight graphs.-knight graph-queen graph-knight graph-queen graphThe knight graph is implemented in the Wolfram Language as KnightTourGraph[m, n], and precomputed properties are available in using GraphData["Knight", m, n].Closed formulas for the numbers of -graph cycles of the knight graph are given by for odd and(1)(E. Weisstein, Nov. 16, 2014).A knight's path is a sequence of moves by a..

### King graph

The king graph is a graph with vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a king.The number of edges in the king graph is , so for , 2, ..., the first few values are 0, 6, 20, 42, 72, 110, ... (OEIS A002943).The order graph has chromatic number for and for . For , 3, ..., the edge chromatic numbers are 3, 8, 8, 8, 8, ....King graphs are implemented in the Wolfram Language as GraphData["King", m, n].All king graphs are Hamiltonian and biconnected. The only regular king graph is the -king graph, which is isomorphic to the tetrahedral graph . The -king graphs are planar only for (with the case corresponding to path graphs) and , some embeddings of which are illustrated above.The -king graph is perfect iff (S. Wagon, pers. comm., Feb. 22, 2013).Closed formulas for the numbers of -cycles of with are given by(1)(2)(3)(4)where the formula for appears in Perepechko and Voropaev.The..

### Trail

A trail is a walk , , , ..., with no repeated edge. The length of a trail is its number of edges.A -trail is a trail with first vertex and last vertex , where and are known as the endpoints.A trail is said to be closed if its endpoints are the same.For a simple graph (which has no multiple edges),a trail may be specified completely by an ordered list of vertices (West 2000, p. 20).

### Traceable graph

A traceable graph is a graph that possesses a Hamiltonian path. Hamiltonian graphs are therefore traceable, but the converse is not necessarily true. The numbers of traceable graphs on , 2, ... are 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864), where the singleton graph is conventionally considered traceable. The first few are illustrated above, with a Hamiltonian path indicated in orange for each.Every self-complementary graph is traceable(Clapham 1974; Camion 1975; Farrugia 1999, p. 52).The following table lists some named graphs that are traceable but not Hamiltonian.graph theta-0 graph7Petersen graph10Herschel graph11Blanuša snarks18flower snark20Coxeter graph28double star snark30Tutte's graph46Szekeres snark50McLaughlin graph276

### Hypotraceable graph

A graph is a hypotraceable graph if has no Hamiltonian path (i.e., it is not a traceable graph), but has a Hamiltonian path (i.e., is a traceable graph) for every (Bondy and Murty 1976, p. 61).There are no hypotraceable graphs on ten or fewer nodes (E. Weisstein, Dec. 11, 2013). In fact, the nonexistence of hypotraceable graphs on small numbers of vertices led T. Gallai to conjecture that no such graphs exist. This conjecture was refuted when a hypotraceable graph with 40 vertices was subsequently found by Horton (Grünbaum 1974, Thomassen 1974). Thomassen (1974) then showed that there exists a hypotraceable graph with vertices for , 37, 39, 40, and all . The smallest of these is the 34-vertex Thomassen graph (left figure above; Thomassen 1974; Bondy and Murty 1976, pp. 239-240).Walter (1969) gave an example of a connected graph in which the longest paths do not have a vertex in common, a property shared by hypotraceable..

### Eulerian path

An Eulerian path, also called an Euler chain, Euler trail, Euler walk, or "Eulerian" version of any of these variants, is a walk on the graph edges of a graph which uses each graph edge in the original graph exactly once. A connected graph has an Eulerian path iff it has at most two graph vertices of odd degree.

### Tait's hamiltonian graph conjecture

The conjecture that every cubic polyhedral graph is Hamiltonian. It was proposed by Tait in 1880 and refuted by Tutte (1946) with the counterexample on 46 vertices (Lederberg 1965) now known as Tutte's graph. Had the conjecture been true, it would have implied the four-color theorem.The following table summarizes some named counterexamples, illustrated above. The smallest examples known has 38 vertices (Lederberg 1965), and was apparently also discovered by D. Barnette and J. Bosák around the same time.graphreference38Barnette-Bośak-Lederberg graphLederberg (1965), Thomassen (1981), Grünbaum (2003, Fig. 17.1.5)42Faulkner-Younger graph 42Faulkner and Younger (1974)42Grinberg graph 42Faulkner and Younger (1974)44Faulkner-Younger graph 44Faulkner and Younger (1974)44Grinberg graph 44Sachs (1968), Berge (1973), Read and Wilson (1998, p. 274)46Grinberg graph 46Bondy..

### Eulerian graph

An Eulerian graph is a graph containing an Eulerian cycle. The numbers of Eulerian graphs with , 2, ... nodes are 1, 1, 2, 3, 7, 15, 52, 236, ... (OEIS A133736), the first few of which are illustrated above.The corresponding numbers of connected Eulerian graphs are 1, 0, 1, 1, 4, 8, 37, 184, 1782, ... (OEIS A003049; Robinson 1969; Liskovec 1972; Harary and Palmer 1973, p. 117), the first few of which are illustrated above.Some care is needed in interpreting the term, however, since some authors define an Euler graph as a different object, namely a graph for which all vertices are of even degree (motivated by the following theorem). Euler showed (without proof) that a connected simple graph is Eulerian iff it has no graph vertices of odd degree (i.e., all vertices are of even degree). While the number of connected Euler graphs on nodes is equal to the number of connected Eulerian graphs on nodes, the counts are different for disconnected graphs since..

### Hamiltonian walk

A Hamiltonian walk on a connected graph is a closed walk of minimal length which visits every vertex of a graph (and may visit vertices and edges multiple times). For example, a Hamiltonian walk on the above 3-pan graph is given by the vertex sequence 4, 3, 1, 2, 3, 4 and hence is of length 5.The length of a Hamiltonian walk in a graph is called the Hamiltonian number . A Hamiltonian graph has , where is the vertex count. A graph with is said to be almost Hamiltonian.

### Hamiltonian number

The Hamiltonian number of a connected graph is the length of a Hamiltonian walk . For a Hamiltonian graph, , where is the vertex count. The Hamiltonian number therefore gives one measure of how far away a graph is from being Hamiltonian, and a graph with is called an almost Hamiltonian graph.Punnim et al. (2007) show thatwith iff is a tree. Since a tree has Hamiltonian number , an almost Hamiltonian tree must satisfy , giving . Since the 3-path graph is the only tree on three nodes, it is also the only almost Hamiltonian tree.If is an almost Hamiltonian cubic graph with vertices, then the triangle-replaced graph has Hamiltonian number(Punnim et al. 2007).Values for special classes of graphs are summarized in the table below, where denotes the vertex count of the graphgraph generalized Petersen graph Hamiltonian graphtree..

### Euler graph

The term "Euler graph" is sometimes used to denote a graph for which all vertices are of even degree (e.g., Seshu and Reed 1961). Note that this definition is different from that of an Eulerian graph, though the two are sometimes used interchangeably and are the same for connected graphs.The numbers of Euler graphs with , 2, ... nodes are 1, 1, 2, 3, 7, 16, 54, 243, 243, 2038, ... (OEIS A002854; Robinson 1969; Mallows and Sloane 1975; Buekenhout 1995, p. 881; Colbourn and Dinitz 1996, p. 687), the first few of which are illustrated above. There is an explicit formula giving these numbers.There are more Euler graphs than Eulerian graphs since there exist disconnected graphs having multiple disjoint cycles with each node even but for which no single cycle passes through all edges. The numbers of Euler-but-not-Eulerian graphs on , 2, ... nodes are 0, 0, 0, 0, 0, 1, 2, 7, 20, 76, 334, 2498, ... (OEIS A189771), the first few of which are..

### Snake

A snake is an Eulerian path in the -hypercube that has no chords (i.e., any hypercube edge joining snake vertices is a snake edge). Klee (1970) asked for the maximum length of a -snake. Klee (1970) gave the bounds(1)for (Danzer and Klee 1967, Douglas 1969), as well as numerous references. Abbott and Katchalski (1988) show(2)and Snevily (1994) showed that(3)for , and conjectured(4)for . The first few values for for , 2, ..., are 2, 4, 6, 8, 14, 26, ... (OEIS A000937).

### Hamiltonian graph

A Hamiltonian graph, also called a Hamilton graph, is a graph possessing a Hamiltonian cycle. A graph that is not Hamiltonian is said to be nonhamiltonian.A Hamiltonian graph on nodes has graph circumference .While it would be easy to make a general definition of "Hamiltonian" that goes either way as far as the singleton graph is concerned, defining "Hamiltonian" to mean "has a Hamiltonian cycle" and taking "Hamiltonian cycles" to be a subset of "cycles" in general would lead to the convention that the singleton graph is nonhamiltonian (B. McKay, pers. comm., Oct. 11, 2006). However, by convention, the singleton graph is generally considered to be Hamiltonian (B. McKay, pers. comm., Mar. 22, 2007). The convention in this work and in GraphData is that is Hamiltonian, while is nonhamiltonian.The numbers of simple Hamiltonian graphs on nodes for , 2, ... are..

### Seymour conjecture

Seymour conjectured that a graph of order with minimum vertex degree contains the th graph power of a Hamiltonian cycle, generalizing Pósa's Conjecture. Komlós et al. (1998) proved the conjecture for sufficiently large using Szemerédi's regularity lemma and a technique called the blow-up lemma.

### Cycle polynomial

One would think that by analogy with the matching-generating polynomial, independence polynomial, etc., a cycle polynomial whose coefficients are the numbers of cycles of length would be defined. While no such polynomial seems not to have been defined in the literature (instead, "cycle polynomials" commonly instead refers to a polynomial corresponding to cycle indices of permutation groups), they are defined in this work.The cycle polynomial, perhaps defined here for the first time, is therefore the polynomialwhose coefficients give the number of simple cycles present in a graph on nodes.Since the smallest possible cycle is of length 3, cycle polynomials have polynomial degree at least 3. The polynomial degree of is the girth of , and the graph is Hamiltonian iff the degree equals .In particular, gives the number of Hamiltonian cycles, so a graph is Hamiltonian iff . A graph is triangle-free iff , and square-free iff .Since cycle..

### Cycle chord

A chord of a graph cycle is an edge not in the edge set of whose endpoints lie in the vertex set (West 2000, p. 225). For example, in the diamond graph as labeled above, the edge is a chord of the cycle .A graph cycle possessing no chord is said to be a chordless cycle, and chordless cycles are important in the study and characterization of perfect graphs.A graph in which every graph cycle possesses a chord (i.e., in which no chordless cycles exists) is said to be a chordal graph. Similarly, a graph in which no chords exist is said to be a chordless graph.

### Circuit rank

The circuit rank , also denoted (Volkmann 1996, Babić et al. 2002) and known as the cyclomatic number, is the smallest number of graph edges which must be removed from a graph on graph edges and nodes such that no graph cycle remains. It is given by(1)for a graph with connected components.The circuit rank provides an inequality on the total number of undirected graph cycles given by(2)(Kirchhoff 1847, Ahrens 1897, König 1936, Volkmann 1996). Furthermore,(3)iff any two cycles have no edge in common (Volkmann 1996). Among connected graphs, the equality therefore holds for (and only for) cactus graphs. Mateti and Deo (1976) proved that there are "essentially" only four graphs with : the complete graphs and , the complete bipartite graph , and (Volkmann 1996).Unless otherwise stated, hydrogen atoms are usually ignored in the computation of such indices as organic chemists usually do when they write a benzene ring as a hexagon..

### Hamilton decomposition

A Hamilton decomposition (also called a Hamiltonian decomposition; Bosák 1990, p. 123) of a Hamiltonian regular graph is a partition of its edge set into Hamiltonian cycles. The figure above illustrates the six distinct Hamilton decompositions of the pentatope graph .The definition is sometimes extended to a decomposition into Hamiltonian cycles for a regular graph of even degree or into Hamiltonian cycles and a single perfect matching for a regular graph of odd degree (Alspach 2010), with a decomposition of the latter type being known as a quasi-Hamilton decomposition (Bosák 1990, p. 123).For a cubic graph, a Hamilton decomposition is equivalent to a single Hamiltonian cycle. For a quartic graph, a Hamilton decomposition is equivalent to a Hamiltonian cycle , the removal of whose edges leaves a connected graph. When this connected graph exists, it gives the second of the pair of Hamiltonian cycles which together..

### Chordless graph

A chordless graph is a simple graph possessing no chords.A chordal graph (which possesses no chordless cycles) is not the same as (or converse of) a chordless graph (which possesses no chords). For example, the square graph is chordless but not chordal, the diamond graph and tetrahedral graph are chordal but not chordless, and empty graphs , path graphs , and the triangle graph are both chordal and chordless.The numbers of connected simple chordless graphs on , 2, ... nodes are 1, 1, 2, 4, 10, 27, ... (OEIS A287693), the first few of which are illustrated above.The numbers of not-necessarily connected simple chordless graphs on , 2, ... nodes are 1, 2, 4, 9, 21, 56, ... (OEIS A287694), the first few of which are illustrated above.

### Chordless cycle

A chordless cycle of a graph is a graph cycle of length at least four in that has no cycle chord (i.e., the graph cycle is an induced subgraph). A chordal graph is a simple graph possessing no chordless cycles. A chordless cycle is sometimes also called a graph hole (Chvátal).A graph is perfect iff neitherthe graph nor its complement has a chordless cycle of odd order.If a chordless 5-cycle exists in a graph , one also exists in its graph complement since in the complement the interior diagonals are really edges in the original. In addition, if no 5-cycle exists in , then no chordless cycle exists in (S. Wagon,. pers. comm., Feb. 2013).No chordless cycles of length greater than exist in a graph with independence number .No chordless cycles of length greater than exist in the graph complement of a graph with , where is the clique covering number and is the clique number.Every cycle of a cactus graph is chordless, but there exist graphs..

### Queen graph

The queen graph is a graph with vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a queen. The -queen graphs have nice embeddings, illustrated above. In general, the default embedding with vertices corresponding to squares of the chessboard has degenerate superposed edges, the only nontrivial exception being the -queen graph.Queen graphs are implemented in the Wolfram Language as GraphData["Queen", m, n].The following table summarized some special cases of queen graphs.namecomplete graph tetrahedral graph The following table summarizes some named graph complements of queen graphs.-queen graph-knight graph-queen graph-queen graph-knight graphAll queen graphs are Hamiltonian and biconnected. The only planar and only regular queen graph is the -queen graph, which is isomorphic to the tetrahedral graph .The only perfect queen graphs are , , and .A closed formula..

### Chordal graph

A chordal graph is a simple graph in which every graph cycle of length four and greater has a cycle chord. In other words, a chordal graph is a graph possessing no chordless cycles.The numbers of simple chordal graphs on , 2, ... nodes are 1, 2, 4, 10, 27, 94, 393, ... (OEIS A048193). The first few are illustrated above, though many are trivially chordal since they possess no cycles of length .The corresponding numbers of simple connected chordal graphs are 1, 1, 2, 5, 15, 58, 272, ... (OEIS A048192). The first few are illustrated above, though many are again chordal only trivially.A split graph is a simple graph whose vertices can be partitioned into a clique and an independent (stable) set. Split graphs are a special class of chordal graphs (Brandstadt et al. 1999).Every chordal graph is perfect.It is possible to recognize chordal graphs in linear time. Furthermore, a maximum clique of a chordal graph can be found in polynomial time although the problem..

### Pseudotree

A pseudotree is a connected pseudoforest, i.e., an undirected connected graph that contains at most one graph cycle. Connected acyclic graphs (i.e., trees), are therefore pseudotrees.Some care is needed when encountering pseudotrees as some authors use the term to mean "a pseudotree that is not a tree." Such graphs are perhaps better known as connected unicyclic graphs for clarity.The numbers of pseudotrees on 1, 2, 3, ... vertices are 1, 1, 2, 4, 8, 19, 44, 112, ... (OEIS A005703), the first few of which are illustrated above.

### Pseudoforest

A pseudoforest is an undirected graph in which every connected component contains at most one graph cycle. A pseudotree is therefore a connected pseudoforest and a forest (i.e., not-necessarily-connected acyclic graph) is a trivial pseudoforest.Some care is needed when encountering pseudoforests as some authors use the term to mean "a pseudoforest that is not a forest."The numbers of pseudoforests on 1, 2, 3, ... vertices are 1, 2, 4, 9, 19, 46, 108, 273 ... (OEIS A134964), the first few of which are illustrated above.

### P&oacute;sa's theorem

There are several related theorems involving Hamiltoniancycles of graphs that are associated with Pósa.Let be a simple graph with graph vertices. 1. If, for every in , the number of graph vertices of vertex degree not exceeding is less than , and 2. If, for odd, the number of graph vertices with vertex degree not exceeding is less than or equal to , then contains a Hamiltonian cycle.Kronk (1969) generalized this result as follows. Let be a simple graph with graph vertices, and let . Then the following conditions are sufficient for to be -line Hamiltonian: 1. For all integers with , the number of graph vertices of vertex degree not exceeding is less than , 2. The number of points of degree not exceeding does not exceed . Pósa (1963) generalized a result of Dirac by proving that every finite simple graph with a sufficiently large valencies of all (or, in some cases, of almost all) vertices and with a sufficiently large number of vertices satisfies..

### Grinberg formula

A formula satisfied by all Hamiltonian cycles with nodes. Let be the number of regions inside the circuit with sides, and let be the number of regions outside the circuit with sides. If there are interior diagonals, then there must be regions(1)Any region with sides is bounded by graph edges, so such regions contribute to the total. However, this counts each diagonal twice (and each graph edge only once). Therefore,(2)Take (2) minus (1),(3)Similarly,(4)so(5)

### P&oacute;sa's conjecture

Dirac (1952) proved that if the minimum vertex degree for a graph on nodes, then contains a Hamiltonian cycle (Bollobás 1978, Komlós et al. 1996).In 1962, Pósa conjectured that contains a square of a Hamiltonian cycle if (Erdős 1964, p. 159; Komlós et al. 1996), where a graph contains the square of a Hamiltonian cycle if there is a Hamiltonian cycle such that , for , 2, ..., .Komlós et al. (1996) proved that there exists a natural number such that if a graph has order and minimum vertex degree at least , then contains the square of a Hamiltonian cycle. This proved Pósa's conjecture (Erdős 1964) for sufficiently large . Kierstead and Quintana (1998) proved Pósa's conjecture for graphs containing a 4-clique .The conjecture was generalized by Seymour (1974) to state that if , then contains the th power of a Hamiltonian cycle (Komlós et al. 1996)...

### Graph path

A path in a graph is a subgraph of that is a path graph (West 2000, p. 20).An -path is a path whose endpoints (vertices of degree 1) are the vertices with indices and . (The symbols and are also commonly used.) A single -path may be found in the Wolfram Language using FindPath[g, s, t], while FindPath[g, s, t, kspec, n] finds at most paths of length kspec (where kspec may be Infinity and may be All).The length of a path is the number of edges it contains.For a simple graph, a path is equivalent to a trail and is completely specified by an ordered sequence of vertices. For a simple graph , a Hamiltonian path is a path that includes all vertices of (and whose endpoints are not adjacent).The number of (undirected) -walks from vertex to vertex in a graph with adjacency matrix is given by the element of (Festinger 1949). In order to compute the number of graph paths, all closed -walks that are not paths must be subtracted. The first few matrices of -paths can be given..

### Planar hypotraceable graph

A planar hypotraceable graph is a hypotraceable graph that is also planar. A number of planar hypotraceable graphs are illustrated above.Using a theorem of Thomassen (1974), the Wiener-Araya graph on 42 vertices can be used to construct a planar hypotraceable graph on 162 vertices, smaller than the 186-vertex graph obtained from the 48-Zamfirescu graph using Thomassen's construction. These graphs are implemented in the Wolfram Language as GraphData["PlanarHypohamiltonian", 162] and GraphData["PlanarHypohamiltonian", 186], respectively.Jooyandeh et al. (2017) showed that there exist planar hypotraceable graphson 154 vertices, as well as on all vertex counts greater than or equal to 156.Using the 70-node Araya-Wiener graph, a 340-nodecubic planar hypotraceable graph can be constructed (Araya and Wiener 2011).Holton and Sheehan (1993) asked if there exists an integer such that a cubic planar hypotraceable..

### Graph hole

An alternative name for a chordless cycle, often simply called a "hole" (Chvátal). Graph holes are called even if they have an even number of vertices and odd if they have an odd number of vertices. The graph complement of a hole is called a graph antihole. No odd hole is a perfect graph (since the clique number of an odd hole is 2 and its chromatic number is 3).

### Path polynomial

One would think that by analogy with the matching-generating polynomial, independence polynomial, etc., a path polynomial whose coefficients are the numbers of paths of length would be defined. While no such polynomial seems not to have been defined in the literature, they are defined in this work.The path polynomial, perhaps defined here for the first time, is therefore the polynomialwhose coefficients give the number of simple paths of length present in a graph on nodes.Since the smallest possible path is of length 1, path polynomials have polynomial degree at least 1. In particular, , where is the edge count of a graph .A graph is traceable iff the degree of the path polynomial equals . In particular, gives the number of Hamiltonian paths, so a graph is traceable iff .Since path counts in a disconnected graph are the sum of path counts in its connected components, the path polynomial is additive over connected components...

### Ore's theorem

If a graph has graph vertices such that every pair of the graph vertices which are not joined by a graph edge has a sum of valences which is , then is Hamiltonian.A graph satisfying Ore's criterion is known as an Ore graph.

### Almost hamiltonian graph

There are several definitions of "almost Hamiltonian" in use.As defined by Punnim et al. (2007), an almost Hamiltonian graph is a graph on nodes having Hamiltonian number .As defined by Sanders (1987), a graph with vertices is almost Hamiltonian if every subset of vertices is contained in a circuit, a definition which is similar to that for a maximally nonhamiltonian graph.This work adopts the definition of Punnim et al. (2007). The numbers of almost Hamiltonian graphs of this type on , 2, ... vertices are 0, 0, 1, 1, 7, 28, 257, 2933, ... (OEIS A185360), the first few of which are illustrated above.Punnim et al. (2007) showed that the generalized Petersen graph is almost Hamiltonian iff and .Punnim et al. (2007) proved that there exists an almost Hamiltonian cubic graph for every even order . The Petersen graph is the unique almost Hamiltonian cubic graph on 10 vertices, and Tietze's graph is the unique almost Hamiltonian cubic graph on..

### Markstr&ouml;m graph

The Markström graph is a cubic planar graph on 24 vertices which lacks cycles of length 4 and 8 but contains cycles of length 16. (In particular, it contains cycles of lengths 3, 5, 6, 7, and 9-24.)This graph is related to the open Erdős-Gyárfás conjecture, which posits that any graph with minimum vertex degree 3 contains a simple cycle whose length is a power of two. Gordon Royle and Klas Markström showed that any counterexample must have at least 17 vertices and that any cubic counterexample must have at least 30 vertices. Markström found four graphs on 24 vertices in which the only power-of-two cycles has 16 vertices; the Markström graph is the only planar graph of these four.

### Forest

A forest is an acyclic graph (i.e., a graph without any graph cycles). Forests therefore consist only of (possibly disconnected) trees, hence the name "forest."Examples of forests include the singleton graph,empty graphs, and all trees.A forest with components and nodes has graph edges. The numbers of forests on , 2, ... nodes are 1, 2, 3, 6, 10, 20, 37, ... (OEIS A005195).A graph can be tested to determine if it is acyclic (i.e., a forest) in the Wolfram Language using AcylicGraphQ[g]. A collection of acyclic graphs is available as GraphData["Acyclic"] or GraphData["Forest"].The total numbers of trees in all the forests of orders , 2, ... are 1, 3, 6, 13, 24, 49, 93, 190, 381, ... (OEIS A005196). The average numbers of trees are therefore 1, 3/2, 2, 13/6, 12/5, 49/20, 93/37, 5/2, ... (OEIS A095131 and A095132).The triangle of numbers of -node forests containing trees is 1; 1, 1; 1, 1, 1; 2, 2, 1, 1; 3, 3, 2, 1, 1; ... (OEIS..

### Acyclic graph

An acyclic graph is a graph having no graph cycles.Acyclic graphs are bipartite.A connected acyclic graph is known as a tree, and a possibly disconnected acyclic graph is known as a forest (i.e., a collection of trees).The numbers of acyclic graphs (forests) on , 2, ... are 1, 2, 3, 6, 10, 20, 37, 76, 153, ... (OEIS A005195), and the corresponding numbers of connected acyclic graphs (trees) are 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, ... (OEIS A000055).A graph can be tested in the Wolfram Language to see if it is acyclic using AcyclicGraphQ[g], and a collection of acyclic graphs are available as GraphData["Acyclic"].A graph with a single cycle is known as a unicyclicgraph.

### Singleton graph

The singleton graph is the graph consisting of a single isolated node with no edges. It is therefore the empty graph on one node. It is commonly denoted (i.e., the complete graph on one node).By convention, the singleton graph is considered to be Hamiltonian(B. McKay, pers. comm., Mar. 22, 2007).

### Matchstick graph

A matchstick graph is a simple graph which has a graph embedding that is planar, for which all distances between vertices have unit distance, and which is non-degenerate (so no vertices are coincident, no edges cross or overlap, and no vertices are coincident with edges on which they are not incident).A matchstick graph is therefore both planar and unit-distance, but a planar unit-distance graph may fail to be a matchstick graph if a single embedding cannot be constructed having both properties. Examples include the prism graphs and Moser spindle, with the sole 6-vertex connected planar unit-distance non-matchstick graph being the 3-prism graph . The numbers of connected graphs on , 2, ... vertices that are planar and unit-distance but not matchstick are 0, 0, 0, 0, 0, 1, 13, ... (E. Weisstein, Apr. 30, 2018), where the 7-vertex examples are illustrated above.The numbers of connected matchstick graphs on , 2, ... nodes are 1, 1, 2,..

### Determined by spectrum

Two nonisomorphic graphs can share the same graph spectrum, i.e., have the same eigenvalues of their adjacency matrices. Such graphs are called cospectral. For example, the graph union and star graph , illustrated above, both have spectrum (Skiena 1990, p. 85). This is the smallest pair of simple graphs that are cospectral. Determining which graphs are uniquely determined by their spectra is in general a very hard problem.Only a small fraction of graphs are known to be so determined, but it is conceivablethat almost all graphs have this property (van Dam and Haemers 2002).In the Wolfram Language, graphs knownto be determined by their spectra are identified as GraphData["DeterminedBySpectrum"].The numbers of simple graphs on , 2, ... nodes that are determined by spectrum are 1, 2, 4, 11, 32, 146, 934, 10624, 223629, ... (OEIS A178925), while the corresponding numbers not determined by spectrum are 0, 0, 0, 0, 2, 10, 110, 1722,..

### Strongly regular graph

A -regular simple graph on nodes is strongly -regular if there exist positive integers , , and such that every vertex has neighbors (i.e., the graph is a regular graph), every adjacent pair of vertices has common neighbors, and every nonadjacent pair has common neighbors (West 2000, pp. 464-465). A graph that is not strongly regular is said to be weakly regular.The complete graph is strongly regular for all . The status of the trivial singleton graph is unclear. Opinions differ on if is a strongly regular graph, though since it has no well-defined parameter, it is preferable to consider it not to be strongly regular (A. E. Brouwer, pers. comm., Feb. 6, 2013).The graph complement of a non-empty non-complete strongly regular graph with parameters is another strongly regular graph with parameters .A number of strongly regular graphs are implemented in the WolframLanguage as GraphData["StronglyRegular"].The..

### Harborth graph

The Harborth graph is the smallest known 4-regular matchstick graph. It is therefore both planar and unit-distance. It has 104 edges and 52 vertices. This graph was named after its discoverer H. Harborth, who first presented it to a general public in 1986 (Harborth 1994, Petersen 1996, Gerbracht 2006).The Harborth graph is implemented in the WolframLanguage as GraphData["HarborthGraph"].Analytic expressions for the vertices consisting of algebraic numbers of degree 22 (with large coefficients) were derived by Gerbracht (2006). As a consequence, Gerbracht (2006) also proved that the Harborth graph is rigid.

### Snark

A snark is a connected bridgeless cubic graph (i.e., a biconnected cubic graph) with edge chromatic number of four. (By Vizing's theorem, the edge chromatic number of every cubic graph is either three or four, so a snark corresponds to the special case of four.) Snarks are therefore class 2 graphs.In order to avoid trivial cases, snarks are commonly restricted to be connected (so that the graph union of two Petersen graphs is excluded), have girth 5 or more and not to contain three edges whose deletion results in a disconnected graph, each of whose components is nontrivial (Read and Wilson 1998, p. 263).Snarks that are trivial in the above senses are sometimes called "reducible" snarks. A number of reducible snarks are illustrated above.The Petersen graph is the smallest snark, and Tutte conjectured that all snarks have Petersen graph graph minors. This conjecture was proven in 2001 by Robertson, Sanders, Seymour, and Thomas,..

### Maximum leaf number

The maximum leaf number of a graph is the largest number of tree leaves in any of its spanning trees.The maximum leaf number and connected domination number of a graph are connected bywhere is the vertex count of .Many families of graphs have simple closed forms, as summarized in the following table. In the table, denotes the floor function.graph familymaximum leaf numberAndrásfai graphantiprism graphApollonian networkbarbell graphblack bishop graph book graph cocktail party graph complete bipartite graph complete bipartite graph complete graph complete tripartite graph complete tripartite graph -crossed prism graphcrown graph cycle graph 2gear graphhelm graphladder graph Möbius ladder pan graph3path graph 2prism graph rook complement graph rook graph star graph sun graphsunlet graph triangular graphweb graphwheel graph white bishop graph ..

### Cayley tree

A tree in which each non-leaf graph vertex has a constant number of branches is called an -Cayley tree. 2-Cayley trees are path graphs. The unique -Cayley tree on nodes is the star graph. The illustration above shows the first few 3-Cayley trees (also called trivalent trees, binary trees, or boron trees). The numbers of binary trees on , 2, ... nodes (i.e., -node trees having vertex degree either 1 or 3; also called 3-Cayley trees, 3-valent trees, or boron trees) are 1, 1, 0, 1, 0, 1, 0, 1, 0, 2, 0, 2, 0 ,4, 0, 6, 0, 11, ... (OEIS A052120).The illustrations above show the first few 4-Cayley and 5-Cayley trees.The percolation threshold for a Cayley tree having branches is

### Taylor's condition

For a given positive integer , does there exist a weighted tree with graph vertices whose paths have weights 1, 2, ..., , where is a binomial coefficient? Taylor showed that no such tree can exist unless it is a perfect square or a perfect square plus 2. No such trees are known except , 3, 4, and 6.Székely et al. showed computationally that there are no such trees with and 11. They also showed that if there is such a tree on vertices then the maximum vertex degree is at most and that there is no path of length larger than . They conjecture that there are only finitely many such trees.

### Caterpillar graph

A caterpillar graph, caterpillar tree, or simply "caterpillar," is a tree in which every graph vertex is on a central stalk or only one graph edge away from the stalk (in other words, removal of its endpoints leaves a path graph; Gallian 2007). A tree is a caterpillar iff all nodes of degree are surrounded by at most two nodes of degree two or greater.Caterpillar graphs are graceful.The number of caterpillar trees on nodes iswhere is the floor function (Harary and Schwenk 1973). For , 2, ... nodes, this gives 1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, ... (OEIS A005418). The first few caterpillars are illustrated above.The number of noncaterpillar trees on , 8, ... as 1, 3, 11, 34, 99, ... (OEIS A052471). The noncaterpillar trees on nodes are illustrated above.

### Strongly binary tree

A strongly binary tree is a rooted tree for which the root is adjacent to either zero or two vertices, and all non-root vertices are adjacent to either one or three vertices (Finch 2003, p. 298). The numbers of strongly binary trees on , 2, ... nodes are 1, 0, 1, 0, 1, 0, 2, 0, 3, 0, 6, 0, ... (OEIS A001190). The counts are 0 for even, and for odd , where is the number of weakly binary trees on nodes (Finch 2003, p. 298).

### Labeled tree

A tree with its nodes labeled. The number of labeled trees on nodes is , the first few values of which are 1, 1, 3, 16, 125, 1296, ... (OEIS A000272). Cayley (1889) provided the first proof of the number of labeled trees (Skiena 1990, p. 151), and a constructive proof was subsequently provided by Prüfer (1918). Prüfer's result gives an encoding for labeled trees known as Prüfer code (indicated underneath the trees above, where the trees are depicted using an embedding with root at the node labeled 1).The probability that a random labeled tree is centeredis asymptotically equal to 1/2 (Szekeres 1983; Skiena 1990, p. 167).

### Steiner tree

The Steiner tree of some subset of the vertices of a graph is a minimum-weight connected subgraph of that includes all the vertices. It is always a tree. Steiner trees have practical applications, for example, in the determination of the shortest total length of wires needed to join some number of points (Hoffman 1998, pp. 164-165).The determination of a Steiner tree is NP-complete and hard even to approximate. There is 1.55-approximate algorithm due to Robins and Zelikovski (2000), but approximation within 95/94 is known to be NP-hard (Chlebik and Chlebikova 2002).

### Kruskal's algorithm

An algorithm for finding a graph's spanning tree of minimum length. It sorts the edges of a graph in order of increasing cost and then repeatedly adds edges that bridge separate components until the graph is fully connected (Pemmaraju and Skiena 2003, p. 336). By negating the weights for each edge, the algorithm can also be used to find a maximum spanning tree.Kruskal's algorithm is implemented in the Wolfram Language as FindSpanningTree[g, Method -> "Kruskal"].

### Binary tree

A binary tree is a tree-like structure that is rooted and in which each vertex has at most two children and each child of a vertex is designated as its left or right child (West 2000, p. 101). In other words, unlike a proper tree, the relative positions of the children is significant.Dropping the requirement that left and right children are considered unique gives a true tree known as a weakly binary tree (in which, by convention, the root node is also required to be adjacent to at most one graph vertex).The height of a binary tree is the number of levels within the tree. The numbers of binary trees of height , 2, ... nodes are 1, 3, 21, 651, 457653, ... (OEIS A001699). A recurrence equation giving these counts is(1)with .The number of binary trees with nodes are 1, 2, 5, 14, 42, ... (OEIS A000108), which are the Catalan number .For a binary tree of height with nodes,(2)These extremes correspond to a balanced tree (each node except the tree leaves has a left..

### Graphic matroid

Suppose that is a pseudograph, is the edge set of , and is the family of edge sets of graph cycles of . Then obeys the axioms for the circuits of a matroid, and hence is a matroid. Any matroid that can be obtained in this way is a graphic matroid.

### Graph triameter

Das (2018) defines the triameter of a connected graph with vertex set and vertex count at least 3 aswhere is the graph distance between vertices and .

### Chromatically unique graph

Let denote the chromatic polynomial of a finite simple graph . Then is said to be chromatically unique if implies that and are isomorphic graphs, in other words, if is determined by its chromatic polynomial. If and are nonisomorphic but share the same chromatic polynomial, they are said to be chromatically equivalent.Cycle graphs are chromatically unique (Chao and Whitehead 1978), as are Turán graphs (Chao and Novacky 1982).Named graphs that are chromatically nonunique include the 3- and 4-barbell graph, bislit cube, bull graph, claw graph, 3-matchstick graph, Moser spindle, 2-Sierpiński sieve graph, star graphs, triakis tetrahedral graph, and 6- and 8-wheel graphs.The numbers of chromatically nonunique simple graphs on nodes for , 2, ... are 0, 0, 0, 4, 18, 115, 905, 11642, 267398, ... (OEIS A137567), while the corresponding numbers of chromatically unique graphs are 1, 2, 4, 7, 16, 41, 139, 704, 7270, ... (OEIS A137568)...

### Reaching algorithm

The so-called reaching algorithm can solve the shortest path problem (i.e., the problem of finding the graph geodesic between two given nodes) on an -edge graph in steps for an acyclic digraph. This algorithm allows paths such that edges traversed in the direction opposite their orientation have a negative length.No other algorithm can have better complexity because any other algorithm would have to at least examine every edge, which would itself take steps.

### Graph thickness

The thickness (or depth) (Skiena 1990, p. 251; Beineke 1997) or (Harary 1994, p. 120) of a graph is the minimum number of planar subgraphs of needed such that the graph union (Skiena 1990, p. 251).The thickness of a planar graph is therefore , and the thickness of a nonplanar graph satisfies .A lower bound for the thickness of a graph is given by(1)where is the number of edges, is the number vertices, and is the ceiling function (Skiena 1990, p. 251). The example above shows a decomposition of the complete graph into three planar subgraphs. This decomposition is minimal, so , in agreement with the bound .The thickness of a complete graph satisfies(2)except for (Vasak 1976, Alekseev and Gonchakov 1976, Beineke 1997). For , 2, ..., the thicknesses are therefore 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, ... (OEIS A124156).The thickness of a complete bipartite graph is given by(3)except possibly when and are both odd, and with there..

### Chromatically equivalent graphs

Two nonisomorphic graphs are said to be chromatically equivalent if they have identical chromatic polynomials. A graph that does not share a chromatic polynomial with any other nonisomorphic graph is said to be a chromatically unique graph.The chromatically equivalent simple graphs on five or fewer vertices are illustrated above.It appears to be the case that all resistance-equivalentgraphs are also chromatically equivalent.

### Projective plane crossing number

The projective plane crossing number of a graph is the minimal number of crossings with which the graph can be drawn on the real projective plane.All graphs with crossing number 0 or 1 have projective plane crossing number 0.Richter and Siran (1996) computed the crossing number of the complete bipartite graph on an arbitrary surface. Ho (2005) showed that the projective crossing number of is given byFor , 2, ..., the first few values are therefore 0, 0, 0, 2, 4, 6, 10, 14, 18, 24, ... (OEIS A128422).

### Graph spectrum

The set of graph eigenvalues of the adjacency matrix is called the spectrum of the graph. (But note that in physics, the eigenvalues of the Laplacian matrix of a graph are sometimes known as the graph's spectrum.) The spectrum of a graph with -fold degenerate eigenvalues is commonly denoted (van Dam and Haemers 2003) or (Biggs 1993, p. 8; Buekenhout and Parker 1998).The product over the elements of the spectrum of a graph is known as the characteristic polynomial of , and is given by the characteristic polynomial of the adjacency matrix of with respect to the variable .The largest absolute value of a graph's spectrum is known as its spectralradius.The spectrum of a graph may be computed in the Wolfram Language using Eigenvalues[AdjacencyMatrix[g]]. Precomputed spectra for many named graphs can be obtained using GraphData[graph, "Spectrum"].A graph whose spectrum consists entirely of integers is known as an integralgraph.The..

### Graph skewness

The skewness of a graph is the minimum number of edges whose removal results in a planar graph (Harary 1994, p. 124). The skewness is sometimes denoted (Cimikowski 1992).A graph with has toroidal crossing number . (However, there exist graphs with that still have .) satisfies(1)where is the vertex count of and its edge count (Cimikowski 1992).The skewness of a disconnected graph is equalto the sum of skewnesses of its connected components.The skewness of a complete graph is given by(2)of the complete bipartite graph by(3)and of the hypercube graph by(4)(Cimikowski 1992).

### Canonical labeling

A canonical labeling, also called a canonical form, of a graph is a graph which is isomorphic to and which represents the whole isomorphism class of (Piperno 2011). The complexity class of canonical labeling is not known.Efficient labeling methods yield an efficient tests for isomorphicgraphs, as provided for example by nauty, Traces, bliss, and other software implementations.

### Ordered pairs representation

An ordered pair representation is a representation of a directed graph in which edges are specified as ordered pairs or vertex indices. The ordered pairs representation of a directed graph may be computed in the Wolfram Language using List @@@ EdgeList[g], and a graph may be constructed from an ordered pair representation using Graph[DirectedEdge @@@ l].

### Bridgeless graph

A bridgeless graph, also called an isthmus-free graph, is a graph that contains no graph bridges. Examples of bridgeless graphs include complete graphs on nodes, cycle graphs, the diamond graph, empty graphs, and the singleton graph.Connected bridgeless graphs are 2-edge connected and can be tested for in the Wolfram Language using KEdgeConnectedGraphQ[g, 2] or EdgeConnectivity[g] .A graph that is not bridgeless is said to be bridged.The numbers of simple bridgeless graphs on , 2, ... vertices are 1, 1, 2, 5, 16, 77, 582, 8002, ... (OEIS A263914).The numbers of simple connected bridgeless graphs on , 2, ... vertices are 1, 0, 1, 3, 11, 60, 502, 7403 ... (OEIS A007146).

### Bridged graph

A bridged graph is a graph that contains one or more graph bridges. Examples of bridged graphs include path graphs, ladder rung graphs, the bull graph, star graphs, and trees.A graph that is not bridged is said to be bridgeless. A connected bridgeless graph can be tested for in the Wolfram Language using Not[KEdgeConnectedGraphQ[g, 2]] or EdgeConnectivity[g] .The numbers of simple bridged graphs on , 2, ... vertices are 0, 1, 2, 6, 18, 79, 462, 4344, ... (OEIS A263915).The numbers of simple connected bridged graphs on , 2, ... vertices are 0, 1, 1, 3, 10, 52, 351, 3714, 63638, 1912203, ... (OEIS A052446).

### Graph neighborhood

The graph neighborhood of a vertex in a graph is the set of all the vertices adjacent to including itself. More generally, the th neighborhood of is the set of all vertices that lie at the distance from .The subgraph induced by the neighborhood of a graph from vertex is called the neighborhood graph.Note that while "graph neighborhood" generally includes vertices adjacent to together with the vertex itself, the term "graph neighbors" generally means vertices adjacent to excluding itself (e.g., Brouwer et al. 1989), so some care is needed when encountering these terms.

### Block

A block is a maximal biconnected subgraph of a given graph . In the illustration above, the blocks are , , and .If a graph is biconnected, then itself is called a block (Harary 1994, p. 26) or a biconnected graph (Skiena 1990, p. 175).

### Graph geodesic

A shortest path between two graph vertices of a graph (Skiena 1990, p. 225). There may be more than one different shortest paths, all of the same length. Graph geodesics may be found using a breadth-first traversal (Moore 1959) or using Dijkstra's algorithm (Skiena 1990, p. 225). One (of possibly several) graph geodesics of a graph from vertex to vertex can be found in the Wolfram Language using FindShortestPath[g, u, v]. The length of the graph geodesic between these points is called the graph distance between and .The length of the maximum geodesic in a given graph is called the graph diameter, and the length of the minimum geodesic is called the graph radius.The matrix consisting of all graph distances from vertex to vertex is known as the all-pairs shortest path matrix, or more simply, the graph distance matrix...

### Graph genus

The genus of a graph is the minimum number of handles that must be added to the plane to embed the graph without any crossings. Special cases are summarized in the following table (West 2000, p. 266).class0planar graph1toroidal graph2double-toroidal graph3pretzel graphThere are no pretzel graphs on eight or fewer vertices.Duke and Haggard (1972; Harary et al. 1973) gave a criterion for the genus of all graphs on 8 and fewer vertices. Define the double-toroidal graphs(1)(2)(3)where denotes minus the edges of . Then for any subgraph of : 1. if does not contain a Kuratowski graph (i.e., or ), 2. if contains a Kuratowski graph (i.e., is nonplanar) but does not contain any for , 3. if contains any for . The complete graph has genus(4)for , where is the ceiling function (Ringel and Youngs 1968; Harary 1994, p. 118). The values for , 2, ... are 0, 0, 0, 0, 1, 1, 1, 2, 3, 4, 5, 6, 8, 10, ... (OEIS A000933).The complete bipartite graph has genus(5)(Ringel..

### Graph eigenvalue

The eigenvalues of a graph are defined as the eigenvalues of its adjacency matrix. The set of eigenvalues of a graph is called a graph spectrum.The largest eigenvalue absolute value in a graph is called the spectral radius of the graph, and the second smallest eigenvalue of the Laplacian matrix of a graph is called its algebraic connectivity.

### Articulation vertex

An articulation vertex of a connected graph is a vertex whose removal will disconnect the graph (Chartrand 1985). More generally, an articulation vertex is a vertex of a not-necessarily-connected graph whose removal increases the connected component count (Harary 1994, p. 26). Articulation vertices are also called cut-vertices or "cutpoints" (Harary 1994, p. 26).A graph on two or more vertices possessing no articulation vertices is called a biconnected graph. A vertex is an articulation vertex iff it appears in two biconnected components.The endpoints of a graph bridge are articulation vertices unless they both have vertex degree 1. On the other hand, it is possible for a non-bridge edge to have both endpoints be articulation vertices.The Wolfram Language function FindVertexCut[g] returns a vertex cut set of smallest size for a graph, which corresponds to an articulation vertex if the set is of size 1.The analog..

### Minimum vertex cover

A minimum vertex cover is a vertex cover having the smallest possible number of vertices for a given graph. The size of a minimum vertex cover of a graph is known as the vertex cover number and is denoted .Every minimum vertex cover is a minimal vertex cover (i.e., a vertex cover that is not a proper subset of any other cover), but not necessarily vice versa.Finding a minimum vertex cover of a general graph is an NP-complete problem. However, for a bipartite graph, the König-Egeváry theorem allows a minimum vertex cover to be found in polynomial time.A minimum vertex cover of a graph can be computed in the Wolfram Language using FindVertexCover[g]. There is currently no Wolfram Language function to compute all minimum vertex covers.Minimum vertex covers correspond to the complements of maximumindependent vertex sets. ..

### Minimum edge cover

A minimum edge cover is an edge cover having the smallest possible number of edges for a given graph. The size of a minimum edge cover of a graph is known as the edge cover number of and is denoted .Every minimum edge cover is a minimal edge cover (i.e., not a proper subset of any other edge cover), but not necessarily vice versa.Only graphs with no isolated points have an edge cover (and therefore a minimum edge cover).A minimum edge cover of a graph can be computed in the Wolfram Language with FindEdgeCover[g]. There is currently no Wolfram Language function to compute all minimum edge covers of a graph.If a graph has no isolated points, thenwhere is the matching number and is the vertex count of (Gallai 1959, West 2000).

### Graph distance

The distance between two vertices and of a finite graph is the minimum length of the paths connecting them (i.e., the length of a graph geodesic). If no such path exists (i.e., if the vertices lie in different connected components), then the distance is set equal to . In a grid graph the distance between two vertices is the sum of the "vertical" and the "horizontal" distances (right figure above).The matrix consisting of all distances from vertex to vertex is known as the all-pairs shortest path matrix, or more simply, the graph distance matrix.

### Graph coarseness

The coarseness of a graph is the maximum number of edge-disjoint nonplanar subgraphs contained in a given graph . The coarseness of a planar graph is therefore .Harary (1994, pp. 121-122) gives formulas for the coarseness of and .

### Graph circumference

The circumference of a graph is the length of any longest cycle in a graph. Hamiltonian graphs on vertices therefore have circumference of .For a cyclic graph, the maximum element of the detour matrix over all adjacent vertices is one smaller than the circumference.The graph circumference of a self-complementary graph is either (i.e., the graph is Hamiltonian), , or (Furrigia 1999, p. 51).Circumferences of graphs for various classes of nonhamiltonian graphs are summarized in the table below.classcircumferenceerefbarbell graph-bishop graphbook graph 6complete bipartite graph for -cone graphgear graphgrid graph grid graph helm graph-knight graphpan graphsunlet graph web graphwheel graph -windmill graph

### Matching number

The matching number of graph , sometimes known as the edge independence number, is the size of a maximum independent edge set. Equivalently, it is the degree of the matching-generating polynomial(1)where is the number of -matchings of a graph . The notations , , or are sometimes also used. satisfies(2)where is the vertex count of , is the floor function. Equality occurs only for a perfect matching, and graph has a perfect matching iff(3)where is the vertex count of .The matching number of a graph is equal to the independence number of its line graph .The König-Egeváry theorem states that the matching number equals the vertex cover number (i.e., size of the smallest minimum vertex cover) are equal for a bipartite graph.If a graph has no isolated points, then(4)where is the matching number, is the size of a minimum edge cover, and is the vertex count of (West 2000).Precomputed matching numbers for many named graphs are available in the..

### Graph bandwidth

The bandwidth of a graph is the minimum matrix bandwidth among all possible adjacency matrices of graphs isomorphic to . Equivalently, it is the minimum graph dilation of a numbering of a graph. Bandwidth is variously denoted , , or .The bandwidth of the singleton graph is not defined, but the conventions or (Miller 1988) are sometimes adopted.The bandwidth of a disconnected graph is themaximum of the bandwidths of its connected components.The bandwidth of a connected graph satisfies the inequalities(Chinn et al. 1982), where is the vertex count of and is the graph diameter andwhere is the chromatic number.Computing the bandwidth of a graph is NP-hard.Bounds for the bandwidth of a graph have been considered by (Harper 1964), and the bandwidth of the -cube was determined by Harper (Harper 1966, Wang and Wu 2007, Harper 2010).Special cases are summarized in the following table.graphbandwidthantiprism graph4cocktail party graph complete..

### Edge cover polynomial

Let be the number of edge covers of a graph of size . Then the edge cover polynomial is defined by(1)where is the edge count of (Akban and Oboudi 2013).Cycle graphs and complete bipartite graphs are determined by their edge cover polynomials (Akban and Oboudi 2013).The edge cover polynomial is multiplicative over graph components, so for a graph having connected components , , ..., the edge cover polynomial of itself is given by(2)The edge cover polynomial satisfies(3)where is the vertex count of a graph and is its independence polynomial (Akban and Oboudi 2013).The following table summarizes sums for the edge cover polynomials of some common classes of graphs (Akban and Oboudi 2013).graphcomplete bipartite graph complete graph cycle graph path graph The following table summarizes closed forms for the edge cover polynomials of some common classes of graphs.graphbook graph cycle graph helm graphpath graph star graph sunlet graph The following..

### Edge cover number

The size of a minimum edge cover in a graph is known as the edge cover number of , denoted .If a graph has no isolated points, thenwhere is the matching number and is the vertex count of (Gallai 1959, West 2000).

### Edge cover

An edge cover is a subset of edges defined similarly to the vertex cover (Skiena 1990, p. 219), namely a collection of graph edges such that the union of edge endpoints corresponds to the entire vertex set of the graph. Therefore, only graphs with no isolated points have an edge cover.A graph can be tested in the Wolfram Language to see if it is an edge cover of a given graph using EdgeCoverQ[g]. Precomputed edge covers for many named graphs can be looked up using GraphData[graph, "EdgeCovers"].An edge cover having the smallest possible number of edges for a given graph is known as a minimum edge cover. A minimum edge cover of a graph can be found in the Wolfram Language using FindEdgeCover[g]. An edge cover that does not contain any other edge cover as a proper subset is known as a minimal edge cover...

### Triangular snake graph

The triangular snake graph is the graph on vertices with odd defined by starting with the path graph and adding edges for , ..., . The first few are illustrated above, and special cases are summarized in the following table.1singleton graph 3triangle graph 5butterfly graphTriangular snakes are unit-distance and matchstick by construction, perfect. They are graceful when the number of triangles is congruent to 0 or 1 (mod 4) (Moulton 1989, Gallian 2018), which is equivalent to when .

A kayak paddle graph is the graph obtained by joining cycle graphs and by a path of length (Gallian 2018). is isomorphic to the 3-barbell graph.Kayak paddle graphs are planar, cactus, unit-distance and matchstick graphs. They are also bridged and traceable and have arboricity of 2.Litersky (2011) proved that kayak paddle graphs are gracefulwhen: 1. , , 2. (mod 4) for , 3. , (Litersky 2011, Gallian 2018).

### Graph categorical product

The graph categorical product, also called the tensor product, is the graph product denoted and defined by the adjacency relations ( and ).The graph categorical product is known as the bipartite double graph of .

### Y graph

"The" Y-graph is another term used to refer to a clawgraph.The term "Y-graph" is also used to refer to a graph expansion with the Y graph as its base (e.g., Horton and Bouwer 1991). There are exactly four graph expansions with Y-graph base that are symmetric (Biggs 1993, p. 147).graphexpansion 28Coxeter graph(7; 1, 2, 4)56cubic symmetric graph (14; 1, 3, 5)112cubic symmetric graph (28; 1, 3, 9)224cubic symmetric graph (56; 1, 9, 25)

### Graph product

In general, a graph product of two graphs and is a new graph whose vertex set is and where, for any two vertices and in the product, the adjacency of those two vertices is determined entirely by the adjacency (or equality, or non-adjacency) of and , and that of and . There are cases to be decided (three possibilities for each, with the case where both are equal eliminated) and thus there are different types of graph products that can be defined.The most commonly used graph products, given by conditions sufficient and necessary for adjacency, are summarized in the following table (Hartnell and Rall 1998). Note that the terminology is not quite standardized, so these products may actually be referred to by different names by different sources (for example, the graph lexicographic product is also known as the graph composition; Harary 1994, p. 21). Many other graph products can be found in Jensen and Toft (1994).Graph products can be computed using..

### Graph power

The th power of a graph is a graph with the same set of vertices as and an edge between two vertices iff there is a path of length at most between them (Skiena 1990, p. 229). Since a path of length two between vertices and exists for every vertex such that and are edges in , the square of the adjacency matrix of counts the number of such paths. Similarly, the th element of the th power of the adjacency matrix of gives the number of paths of length between vertices and . Graph powers are implemented in the Wolfram Language as GraphPower[g, k].The graph th power is then defined as the graph whose adjacency matrix given by the sum of the first powers of the adjacency matrix,which counts all paths of length up to (Skiena 1990, p. 230).Raising any graph to the power of its graph diameter gives a complete graph. The square of any biconnected graph is Hamiltonian (Fleischner 1974, Skiena 1990, p. 231). Mukhopadhyay (1967) has considered "square..

### Graph automorphism

An automorphism of a graph is a graph isomorphism with itself, i.e., a mapping from the vertices of the given graph back to vertices of such that the resulting graph is isomorphic with . The set of automorphisms defines a permutation group known as the graph's automorphism group. For every group , there exists a graph whose automorphism group is isomorphic to (Frucht 1939; Skiena 1990, p. 185). The automorphism groups of a graph characterize its symmetries, and are therefore very useful in determining certain of its properties.The group of graph automorphisms of a graph may be computed in the Wolfram Language using GraphAutomorphismGroup[g], the elements of which may then be extracted using GroupElements. A number of software implementations exist for computing graph automorphisms, including nauty by Brendan McKay and SAUCY2, the latter of which performs several orders of magnitude faster than other implementations based on empirical..

### Maxcut

Let be a (not necessarily simple) undirected edge-weighted graph with nonnegative weights. A cut of is any nontrivial subset of , and the weight of the cut is the sum of weights of edges crossing the cut. A maxcut is then defined as a cut of of maximum weight. Determining the maxcut of a graph is an NP-hard problem.

### Edge contraction

In a graph , contraction of an edge with endpoints is the replacement of and with a single vertex such that edges incident to the new vertex are the edges other than that were incident with or . The resulting graph has one less edge than .Graph minors are defined in terms of edge contractions.

### Graph isomorphism

Let be the vertex set of a simple graph and its edge set. Then a graph isomorphism from a simple graph to a simple graph is a bijection such that iff (West 2000, p. 7).If there is a graph isomorphism for to , then is said to be isomorphic to , written .There exists no known P algorithm for graph isomorphism testing, although the problem has also not been shown to be NP-complete. As a result, the special complexity class graph isomorphism complete is sometimes used to refer to the problem of graph isomorphism testing.

### Edge automorphism group

The set of all edge automorphisms of , denoted . Let be the line graph of a graph . Then the edge automorphism group is isomorphic to ,(Holton and Sheehan 1993, p. 26).

### Graph intersection

Let be a set and a nonempty family of distinct nonempty subsets of whose union is . The intersection graph of is denoted and defined by , with and adjacent whenever and . Then a graph is an intersection graph on if there exists a family of subsets for which and are isomorphic graphs (Harary 1994, p. 19). Graph intersections can be computed in the Wolfram Language using GraphIntersection[g, h].

### Edge automorphism

An edge automorphism of a graph is a permutation of the edges of that sends edges with common endpoint into edges with a common endpoint. The set of all edge automorphisms of from a group called the edge automorphism group of , denoted .

### I graph

"The" graph is the path graph on two vertices: .An -graph for and is a generalization of a generalized Petersen graph and has vertex setand edge setwhere the subscripts are read modulo (Bouwer et al. 1988, Žitnik et al. ). Such graphs can be constructed by graph expansion on .If the restriction is relaxed to allow and to equal , gives the ladder rung graph and gives the sunlet graph .Two -graphs and are isomorphic iff there exists an integer relatively prime to such that either or (Boben et al. 2005, Horvat et al. 2012, Žitnik 2012).The graph is connected iff . If , then the graph consists of copies of (Žitnik et al. 2012).The -graph corresponds to copies of the graph The following table summarizes special named -graphs and classes of named -graphs.graphcubical graph Petersen graph Dürer graphMöbius-Kantor graphdodecahedral graphDesargues graphNauru graphprism graph generalized Petersen graph All -graphs..

### Graph expansion

Given any tree having vertices of vertex degrees of 1 and 3 only, form an -expansion by taking disjoint copies of and joining corresponding leaves by an -cycle where, however, the th leaf on the th copy need not be connected to the th leaf on the st copy, but will in general be connected to the th copy. The set of values are known as the steps.The resulting graphs are always cubic, and there exist exactly 13 graph expansions that are symmetric as well, as summarized in the following table (Biggs 1993, p. 147). E. Gerbracht (pers. comm., Jan. 29, 2010) has shown that all the graphs in this table are unit-distance.graphFostergeneralized Petersen graphbase graphexpansion 8cubical graph I graph(4; 1, 1)10Petersen graphI graph(5; 1, 2)16Möbius-Kantor graphI graph(8; 1, 3)20dodecahedral graphI graph(10; 1, 2)20Desargues graphI graph(10; 1, 3)24Nauru graphI graph(12; 1, 5)28Coxeter graphY graph(7; 1, 2, 4)48cubic symmetric..

### Tree

A tree is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, since a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph.Trees were first studied by Cayley (1857). McKay maintains a database of trees up to 18 vertices, and Royle maintains one up to 20 vertices.A tree is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph (or, equivalently, a connected forest). A tree with nodes has graph edges. Conversely, a connected graph with nodes and edges is a tree. All trees are bipartite graphs (Skiena 1990, p. 213). Trees with no particular node singled out are sometimes called free trees (or unrooted tree), by way of distinguishing them from rooted trees (Skiena 1990, Knuth 1997).The points of connection are known..

### Generalized moore graph

A generalized Moore graph is a regular graph of degree where the counts of vertices at each distance , 1, ... from any vertex are 1, , , , , ..., with the last distance count not necessarily filled up. That is, all the levels are full except possibly the last which must have the rest. Alternatively, the girth is as great as the naive bound allows and the diameter is as little as the naive bound allows. Stated yet another way, a generalized Moore graph is a regular graph such that the average distance between pairs of vertices achieves the naive lower bound.The numbers of generalized Moore graphs with , 2, ... nodes are 0, 0, 0, 1, 1, 4, 3, 13, 21, ... (OEIS A088933).The numbers of cubic generalized Moore graphs with , 4, 6, ... nodes are 0, 1, 2, 2, 1, 2, 7, 6, 1, 1, ... (OEIS A005007).It is an open problem if there are infinitely many generalized Moore graphs of each degree...

### Percolation theory

Percolation theory deals with fluid flow (or any other similar process) in random media.If the medium is a set of regular lattice points, then there are two main types of percolation: A site percolation considers the lattice vertices as the relevant entities; a bond percolation considers the lattice edges as the relevant entities. These two models are examples of discrete percolation theory, an umbrella term used to describe any percolation model which takes place on a regular point lattice or any other discrete set, and while they're most certainly the most-studied of the discrete models, others such as AB percolation and mixed percolation do exist and are reasonably well-studied in their own right.Contrarily, one may also talk about continuum percolation models, i.e.,models which attempt to define analogous tools and results with respect to continuous, uncountable domains. In particular, continuum percolation theory involves notions..

### Percolation

Percolation, the fundamental notion at the heart of percolation theory, is a difficult idea to define precisely though it is quite easy to describe qualitatively.From the narrowest perspective, the term percolation can be defined as a model of a porous medium; indeed, it is from this perspective that the study of percolation theory blossomed, and is typically agreed to be the fundamental physical situation that modern percolation theory attempts to address.Likewise, it is not uncommon for the term percolation to describe the actual fluid flow within the random media or as the theoretical simulation of such a flow for a given simulated medium.One of the difficulties underlying the formulation of a precise definition is that some authors choose to define the term relative to the machinery used in its study. For instance, some authors choose to define percolation to be the result of independently removing vertices or edges from some sort of graph..

### Disk model

The disk model is the standard Boolean-Poisson model in two-dimensional continuum percolation theory. In particular, the disk model is characterized by the existence of a Poisson process in which distributes the centers of a collection of closed disks (i.e., two-dimensional closed balls) along with a random process which independently assigns random radii to each .The disks which make up the disk model are known as randomdisks.

### Ab percolation

An percolation is a discrete percolation model in which the underlying point lattice graph has the properties that each of its graph vertices is occupied by an atom either of type or of type , that there is a probability that any given vertex is occupied by an atom of type , and that different vertices are occupied independently of each other.In this model, a graph edge of is said to be open if its end vertices are occupied by atoms of different types and is said to be closed otherwise. The idea is based on the hypothesis that dissimilar atoms bond together whereas similar atoms repel one another.This model is sometimes studied under the title antipercolation.

### Zarankiewicz's conjecture

Zarankiewicz's conjecture asserts that graph crossing number for a complete bipartite graph is(1)where is the floor function. The original proof by Zarankiewicz (1954) contained an error, but was subsequently solved in some special cases by Guy (1969). Zarankiewicz (1954) showed that in general, the formula provides an upper bound to the actual number.The problem addressed by the conjecture is sometimes known as the brick factory problem, since it was described by Turán (1977) as follows: "We worked near Budapest, in a brick factory. There were some kilns where the bricks were made and some open storage yards where the bricks were stored. All the kilns were connected to all the storage yards. The bricks were carried on small wheeled trucks to the storage yards. All we had to do was to put the bricks on the trucks at the kilns, push the trucks to the storage yards, and unload them there. We had a reasonable piece rate for the trucks, and..

### Torus grid graph

The torus grid graph is the graph formed from the graph Cartesian product of the cycle graphs and . is isomorphic to . can be formed starting with an grid graph and connecting corresponding left/right and top/bottom vertex pairs with edges. While such an embedding has overlapping edges in the plane, it can naturally be placed on the surface of a torus with no edge intersections or overlaps. Torus grid graphs are therefore toroidal graphs. The isomorphic torus grid graphs and are illustrated above.The torus grid graphs are quartic and Hamiltonianand have vertex count(1)Torus grid graphs are circulant graphs iff and are relatively prime, i.e., . In such cases, is isomorphic to . Special cases are summarized in the following table and illustrated above in attractive (but non-toroidal) embddings.graphcirculant graph generalized quadrangle quartic vertex-transitive graph Qt65tesseract graph Harary et al. (1973) conjectured that(2)for all..

### Smallest cubic crossing number graph

The smallest cubic graphs with graph crossing number have been termed "crossing number graphs" or -crossing graphs by Pegg and Exoo (2009). The -crossing graphs are implemented in the Wolfram Language as GraphData["CrossingNumberGraphNA"], with N being a number and X a letter, for example 3C for the Heawood graph or 8B for cubic symmetric graph .The following table summarizes and updates the smallest cubic graphs having given crossing number, correcting Pegg and Exoo (2009) by and by omitting two of the three unnamed 24-node graphs (CNG 8D and CNG 8E) given as having crossing number 8 (but which actually have crossing number 7), noting that the 26-node graph here called CNG 9A and labeled as "McGee + edge" (corresponding to one of two certain edge insertions in the McGee graph) actually has (not 10), and adding the edge-excised Coxeter graph as CNG 9 B. In addition, the 28-node graphs CNG 10A with crossing number..

### Guy's conjecture

Guy's conjecture, which has not yet been proven or disproven, states that the graph crossing number for a complete graph is(1)where is the floor function, which can be rewritten(2)The values for , 2, ... are then given by 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315, 441, 588, ... (OEIS A000241).Guy (1972) proved the conjecture for , a result extended to by Pan and Richter (2007).It is known that(3)(Richter and Thomassen 1997, de Klerk et al. 2007, Pan and Richter 2007).

### Graph crossing number

Given a "good" graph (i.e., one for which all intersecting graph edges intersect in a single point and arise from four distinct graph vertices), the crossing number is the minimum possible number of crossings with which the graph can be drawn, including using curved (non-rectilinear) edges. Several notational conventions exist in the literature, with some of the more common being (e.g., Pan and Richter 2007; Clancy et al. 2019), , (e.g., Pach and Tóth 2005), and .A graph with crossing number 0 is a planar graph. However, there appears to be no term in standard use for a graph with graph crossing number 1 (the terms "almost planar" and "1-planar" are used in the literature for other concepts). Checking if a graph has crossing number 1 is straightforward using the following algorithm (M. Haythorpe, pers. comm., Apr. 16, 2019). First, confirm that the graph is nonplanar. Then, for all non-adjacent..

### Edge chromatic number

The edge chromatic number, sometimes also called the chromatic index, of a graph is fewest number of colors necessary to color each edge of such that no two edges incident on the same vertex have the same color. In other words, it is the number of distinct colors in a minimum edge coloring.The edge chromatic number of a graph must be at least , the largest vertex degree of the graph (Skiena 1990, p. 216). However, Vizing (1964) and Gupta (1966) showed that any graph can be edge-colored with at most colors. There are therefore precisely two classes of graphs: those with edge chromatic number equal to (class 1 graphs) and those with edge chromatic number equal to (class 2 graphs).By definition, the edge chromatic number of a graph equals the (vertex) chromatic number of the line graph .The edge chromatic number of a graph can be computed using EdgeChromaticNumber[g] in the Wolfram Language package Combinatorica` . Precomputed edge chromatic numbers..

### Soifer graph

The Soifer graph is a planar graph on 9 nodes that tangles the Kempe chains in Kempe's algorithm and thus provides an example of how Kempe's supposed proof of the four-color theorem fails. As proved by Gethner and Springer, the Soifer graph is the smallest such counterexample (and is smaller than the Kittell graph and Errera graph).It is implemented in the Wolfram Languageas GraphData["SoiferGraph"].

### Distinguishing number

A labeling of (the vertices) of a graph with positive integers taken from the set is said to be -distinguishing if no graph automorphism of preserves all of the vertex labels. Formally, is -distinguishing if for every nontrivial , there exists such that , where is the vertex set of and is the automorphism group of . The distinguishing number of of is then the smallest such that has a labeling that is -distinguishing (Albertson and Collins 1996).Different graphs with the same automorphism group may have different distinguishing numbers. iff is an identity graph. The distinguishing number of a graph and its graph complement are the same.A graph with has distinguishing number (Tymoczko 2005; due to Albertson, Collins, and Kleitman).Special cases are summarized in the following table.complete bipartite graph complete graph cycle graph generalized Petersen graph hypercube graph path graph star graph -triangular graph wheel graph ..

### Irredundant ramsey number

Let , , ..., be a -graph edge coloring of the complete graph , where for each , 2, ..., t, is the spanning subgraph of consisting of all graph edges colored with the th color. The irredundant Ramsey number is the smallest integer such that for any -graph edge coloring of , the graph complement has an irredundant set of size for at least one , ..., . Irredundant Ramsey numbers were introduced by Brewster et al. (1989) and satisfyFor a summary, see Mynhardt (1992).boundsreference6Brewster et al. 19898Brewster et al. 198912Brewster et al. 198915Brewster et al. 199018Chen and Rousseau 1995, Cockayne et al. 199113Cockayne et al. 199213Cockayne and Mynhardt 1994

### Schwenk's formula

Let be the number of monochromatic forced triangles (where and are the number of red and blue triangles) in an extremal graph. Thenwhere is a binomial coefficient and is the floor function (Schwenk 1972).

### Heule graphs

Heule graphs are a set of unit-distance graphs with chromatic number five derived by Marijn Heule in April-May 2018 from the 1581-vertex de Grey Graph (Heule 2018). As of July 2019, they provide the smallest known examples that establish the solution to the Hadwiger-Nelson problem (i.e., the chromatic number of the plane) as 5, 6, or 7. The first of these graphs were discovered in the days and weeks following publication of the de Grey graph and are summarized in the following table, with the 529-vertex graph being discovered more than a year later and after roughly 100,000 CPU-hours of computation (Heule 2019). The first few are illustrated above.vertex countedge countdiscovery date8744461Apr. 14, 20188264273Apr. 16, 20188034144Apr. 30, 20186333166May 6, 20186103000May 14, 20185532722May 30, 20185292670Jul. 1, 2019..

### De grey graph

The de Grey graph is the name given here to the 1581-vertex graph presented in de Grey (2018) which demonstrated that the solution to the Hadwiger-Nelson problem (i.e., the chromatic number of the plane) is at least 5. This graph (together with the larger graphs from which it was derived) provided the first known examples of a unit-distance graph with chromatic number 5.Smaller unit-distance graphs with chromatic number 5, here called Heule graphs, were computationally derived from the de Grey graph by Marijn Heule.

### Class 2 graph

Vizing's theorem states that a graph can be edge-colored in either or colors, where is the maximum vertex degree of the graph. A graph with edge chromatic number equal to is known as a class 2 graph.Class 2 graphs include the Petersen graph, complete graphs for , 5, 7, ..., and the snarks.All regular graphs with an odd number of nodes are class 2 by parity. Such graphs automatically have an even number of edges per vertex.A graph is trivially class 2 if the maximum independent edge sets are not large enough to cover all edges. In particular, a graph is trivially class 2 ifwhere is the matching number, the maximum vertex degree, and the edge count of .The following table summarizes some named class 2 graphs.graph triangle graph3pentatope graph5Petersen graph10first Blanuša snark18second Blanuša snark18Robertson graph19flower snark2025-Grünbaum graph25Doyle graph27double star snark30Szekeres snark50McLaughlin graph275The..

### Royle graphs

The Royle graphs are the two unique simple graphs on eight nodes whose sigma polynomials have nonreal roots (Read and Wilson 1998, p. 265). The sigma polynomials of these graphs are given by(1)(2)respectively, each of which has two nonreal roots (and where the members of each pairs are complex conjugates of each other).The Royle graphs are implemented in the Wolfram Language as GraphData["RoyleGraph1"] and GraphData["RoyleGraph2"].The numbers of simple graphs having this property on , 2, ... vertices are 0, 0, 0, 0, 0, 0, 0, 2, 42, ..., with the 42 such graphs on 9 vertices illustrated above.