edit this page

1. Definition

An (undirected, unlabelled and simple) graph $G = (V,E)$ consists of

We consider graphs to be

2. Examples

The four (undirected, unlabelled, simple) graphs on three vertices $\{0,1,2\}$ are

3. Further Definitions

4. Properties

4.1. Subgraphs

Given graphs $G$ and $H$, $H$ is a subgraph of $G$, notated $H\subseteq G$, if

$H$ is a proper subgraph if either

If $V(H)=V(G)$ but $E(H)\subsetneq E(G)$, then $H$ is a spanning subgraph of $G$.

4.2. Edge Counting Theorem

If $G$ is a graph of size $m$, then $\sum_{v\in V(G)} deg(v) = 2m$

4.3. Eularian Graph Criteria

A nontrivial connected graph $G$ is Eularian if and only if every vertex of G has even degree.

4.4. Four Color Theorem

Every planar graph is four-colorable. That is, the chromatic number of a planar graph is at most four.

5. Remarks

A labeled graph is a graph which has all of its vertices labeled.

A multigraph is a graph in which multiple edges between vertices are allowed as well as loops that connect a vertex to itself.

A directed graph or digraph is a graph in which each edge has a specific orientation or direction.

We have the following 123 statistics on Graphs in the database:

St000081 Graphs ⟶ ℤ
The number of edges of a graph.
St000086 Graphs ⟶ ℤ
The number of subgraphs.
St000087 Graphs ⟶ ℤ
The number of induced subgraphs.
St000093 Graphs ⟶ ℤ
The length of the maximal independent set of vertices of a graph.
St000095 Graphs ⟶ ℤ
The number of triangles of a graph.
St000096 Graphs ⟶ ℤ
The number of spanning trees of a graph.
St000097 Graphs ⟶ ℤ
The order of the largest clique of the graph.
St000098 Graphs ⟶ ℤ
The chromatic number of a graph.
St000171 Graphs ⟶ ℤ
The degree of the graph.
St000172 Graphs ⟶ ℤ
The Grundy number of a graph.
St000244 Graphs ⟶ ℤ
The cardinality of the automorphism group of a graph.
St000258 Graphs ⟶ ℤ
The burning number of a graph.
St000259 Graphs ⟶ ℤ
The diameter of a connected graph.
St000260 Graphs ⟶ ℤ
The radius of a connected graph.
St000261 Graphs ⟶ ℤ
The edge connectivity of a graph.
St000262 Graphs ⟶ ℤ
The vertex connectivity of a graph.
St000263 Graphs ⟶ ℤ
The Szeged index of a graph.
St000264 Graphs ⟶ ℤ
The girth of a graph, which is not a tree.
St000265 Graphs ⟶ ℤ
The Wiener index of a graph.
St000266 Graphs ⟶ ℤ
The number of spanning subgraphs of a graph with the same connected components.
St000267 Graphs ⟶ ℤ
The number of maximal spanning forests contained in a graph.
St000268 Graphs ⟶ ℤ
The number of strongly connected orientations of a graph.
St000269 Graphs ⟶ ℤ
The number of acyclic orientations of a graph.
St000270 Graphs ⟶ ℤ
The number of forests contained in a graph.
St000271 Graphs ⟶ ℤ
The chromatic index of a connected graph.
St000272 Graphs ⟶ ℤ
The treewidth of a graph.
St000273 Graphs ⟶ ℤ
The domination number of a graph.
St000274 Graphs ⟶ ℤ
The number of perfect matchings of a graph.
St000276 Graphs ⟶ ℤ
The size of the preimage of the map 'to graph' from Ordered trees to Graphs.
St000283 Graphs ⟶ ℤ
The size of the preimage of the map 'to graph' from Binary trees to Graphs.
St000286 Graphs ⟶ ℤ
The number of connected components of the complement of a graph.
St000287 Graphs ⟶ ℤ
The number of connected components of a graph.
St000299 Graphs ⟶ ℤ
The number of nonisomorphic vertex-induced subtrees.
St000300 Graphs ⟶ ℤ
The number of independent sets of vertices of a graph.
St000301 Graphs ⟶ ℤ
The number of facets of the stable set polytope of a graph.
St000302 Graphs ⟶ ℤ
The determinant of the distance matrix of a connected graph.
St000303 Graphs ⟶ ℤ
The determinant of the product of the incidence matrix and its transpose of a gra....
St000309 Graphs ⟶ ℤ
The number of vertices with even degree.
St000310 Graphs ⟶ ℤ
The minimal degree of a vertex of a graph.
St000311 Graphs ⟶ ℤ
The number of vertices of odd degree in a graph.
St000312 Graphs ⟶ ℤ
The number of leaves in a graph.
St000313 Graphs ⟶ ℤ
The number of degree 2 vertices of a graph.
St000315 Graphs ⟶ ℤ
The number of isolated vertices of a graph.
St000322 Graphs ⟶ ℤ
The skewness of a graph.
St000323 Graphs ⟶ ℤ
The minimal crossing number of a graph.
St000343 Graphs ⟶ ℤ
The number of spanning subgraphs of a graph.
St000344 Graphs ⟶ ℤ
The number of strongly connected outdegree sequences of a graph.
St000349 Graphs ⟶ ℤ
The number of different adjacency matrices of a graph.
St000350 Graphs ⟶ ℤ
The sum of the vertex degrees of a graph.
St000351 Graphs ⟶ ℤ
The determinant of the adjacency matrix of a graph.
St000361 Graphs ⟶ ℤ
The second Zagreb index of a graph.
St000362 Graphs ⟶ ℤ
The size of a minimal vertex cover of a graph.
St000363 Graphs ⟶ ℤ
The number of minimal vertex covers of a graph.
St000364 Graphs ⟶ ℤ
The exponent of the automorphism group of a graph.
St000368 Graphs ⟶ ℤ
The Altshuler-Steinberg determinant of a graph.
St000370 Graphs ⟶ ℤ
The genus of a graph.
St000379 Graphs ⟶ ℤ
The number of Hamiltonian cycles in a graph.
St000387 Graphs ⟶ ℤ
The matching number of a graph.
St000388 Graphs ⟶ ℤ
The number of orbits of vertices of a graph under automorphisms.
St000403 Graphs ⟶ ℤ
The Szeged index minus the Wiener index of a graph.
St000422 Graphs ⟶ ℤ
The energy of a graph, if it is integral.
St000447 Graphs ⟶ ℤ
The number of pairs of vertices of a graph with distance 3.
St000448 Graphs ⟶ ℤ
The number of pairs of vertices of a graph with distance 2.
St000449 Graphs ⟶ ℤ
The number of pairs of vertices of a graph with distance 4.
St000450 Graphs ⟶ ℤ
The number of edges minus the number of vertices plus 2 of a graph.
St000452 Graphs ⟶ ℤ
The number of distinct eigenvalues of a graph.
St000453 Graphs ⟶ ℤ
The number of distinct Laplacian eigenvalues of a graph.
St000454 Graphs ⟶ ℤ
The largest eigenvalue of a graph if it is integral.
St000455 Graphs ⟶ ℤ
The second largest eigenvalue of a graph if it is integral.
St000456 Graphs ⟶ ℤ
The monochromatic index of a connected graph.
St000464 Graphs ⟶ ℤ
The Schultz index of a connected graph.
St000465 Graphs ⟶ ℤ
The first Zagreb index of a graph.
St000466 Graphs ⟶ ℤ
The Gutman (or modified Schultz) index of a connected graph.
St000467 Graphs ⟶ ℤ
The hyper-Wiener index of a connected graph.
St000468 Graphs ⟶ ℤ
The Hosoya index of a graph.
St000469 Graphs ⟶ ℤ
The distinguishing number of a graph.
St000479 Graphs ⟶ ℤ
The Ramsey number of a graph.
St000482 Graphs ⟶ ℤ
The (zero)-forcing number of a graph.
St000535 Graphs ⟶ ℤ
The rank-width of a graph.
St000536 Graphs ⟶ ℤ
The pathwidth of a graph.
St000537 Graphs ⟶ ℤ
The cutwidth of a graph.
St000544 Graphs ⟶ ℤ
The cop number of a graph.
St000552 Graphs ⟶ ℤ
The number of cut vertices of a graph.
St000553 Graphs ⟶ ℤ
The number of blocks of a connected graph.
St000571 Graphs ⟶ ℤ
The F-index (or forgotten topological index) of a graph.
St000636 Graphs ⟶ ℤ
The hull number of a graph.
St000637 Graphs ⟶ ℤ
The length of the longest cycle in a graph.
St000671 Graphs ⟶ ℤ
The maximin edge-connectivity for choosing a subgraph.
St000699 Graphs ⟶ ℤ
The toughness times the least common multiple of 1,.
St000718 Graphs ⟶ ℤ
The largest Laplacian eigenvalue of a graph if it is integral.
St000722 Graphs ⟶ ℤ
The number of different neighbourhoods in a graph.
St000723 Graphs ⟶ ℤ
The maximal cardinality of a set of vertices with the same neighbourhood in a gra....
St000741 Graphs ⟶ ℤ
The Colin de Verdière graph invariant.
St000771 Graphs ⟶ ℤ
The largest multiplicity of a distance Laplacian eigenvalue in a connected graph.....
St000772 Graphs ⟶ ℤ
The multiplicity of the largest distance Laplacian eigenvalue in a connected grap....
St000773 Graphs ⟶ ℤ
The multiplicity of the largest Laplacian eigenvalue in a graph.
St000774 Graphs ⟶ ℤ
The maximal multiplicity of a Laplacian eigenvalue in a graph.
St000775 Graphs ⟶ ℤ
The multiplicity of the largest eigenvalue in a graph.
St000776 Graphs ⟶ ℤ
The maximal multiplicity of an eigenvalue in a graph.
St000777 Graphs ⟶ ℤ
The number of distinct eigenvalues of the distance Laplacian of a connected graph....
St000778 Graphs ⟶ ℤ
The metric dimension of a graph.
St000785 Graphs ⟶ ℤ
The number of distinct colouring schemes of a graph.
St000786 Graphs ⟶ ℤ
The maximal number of occurrences of a colour in a proper colouring of a graph.
St000822 Graphs ⟶ ℤ
The Hadwiger number of the graph.
St000915 Graphs ⟶ ℤ
The Ore degree of a graph.
St000916 Graphs ⟶ ℤ
The packing number of a graph.
St000917 Graphs ⟶ ℤ
The open packing number of a graph.
St000918 Graphs ⟶ ℤ
The 2-limited packing number of a graph.
St000926 Graphs ⟶ ℤ
The clique-coclique number of a graph.
St000948 Graphs ⟶ ℤ
The chromatic discriminant of a graph.
St000972 Graphs ⟶ ℤ
The composition number of a graph.
St000985 Graphs ⟶ ℤ
The number of positive eigenvalues of the adjacency matrix of the graph.
St000986 Graphs ⟶ ℤ
The multiplicity of the eigenvalue zero of the adjacency matrix of the graph.
St000987 Graphs ⟶ ℤ
The number of positive eigenvalues of the Laplacian matrix of the graph.
St001029 Graphs ⟶ ℤ
The size of the core of a graph.
St001056 Graphs ⟶ ℤ
The Grundy value for the game of deleting vertices of a graph until it has no edg....
St001057 Graphs ⟶ ℤ
The Grundy value of the game of creating an independent set in a graph.
St001060 Graphs ⟶ ℤ
The distinguishing index of a graph.
St001069 Graphs ⟶ ℤ
The coefficient of the monomial xy of the Tutte polynomial of the graph.
St001070 Graphs ⟶ ℤ
The absolute value of the derivative of the chromatic polynomial of the graph at ....
St001071 Graphs ⟶ ℤ
The beta invariant of the graph.
St001072 Graphs ⟶ ℤ
The evaluation of the Tutte polynomial of the graph at x and y equal to 3.
St001073 Graphs ⟶ ℤ
The absolute value of the evaluation of the Tutte polynomial of the graph at x eq....

6. Maps

We have the following 6 maps from and to Graphs in the database:

Mp00011 Binary trees ⟶ Graphs
to graph
Mp00037 Graphs ⟶ Integer partitions
to partition of connected components
Mp00046 Ordered trees ⟶ Graphs
to graph
Mp00074 Posets ⟶ Graphs
to graph
Mp00111 Graphs ⟶ Graphs
complement
Mp00117 Graphs ⟶ Graphs
Ore closure

7. References

8. Sage examples


CategoryCombinatorialCollection