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 114 statistics 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.

6. Maps

We have the following 6 maps 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