# 1. Definition

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

• a set $V$ of vertices (which we assume for simplicity to be $\{0,\ldots,n-1\}$) and,

• a set $E \subseteq \binom{V}{2}$ of edges.

We consider graphs to be

• undirected: edges are unordered pairs of vertices,

• unlabelled: graphs $G = (V,E)$ and $G' = (V',E')$ are considered equal if there is a permutation $\pi : V \rightarrow V'$ such that $\{u,v\} \in E \Leftrightarrow \{\pi(u),\pi(v)\} \in E'$,

• simple: multiple edges and loops are disallowed.

# 2. Examples

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

• $E_1 = \{\}$,

• $E_2 = \{\{0,1\}\}$,

• $E_3 = \{\{0,1\},\{1,2\}\}$,

• $E_4 = \{\{0,1\},\{1,2\},\{0,2\}\}$.

# 3. Further Definitions

• If $\{u,v\}$ is an edge in a graph $G$, then $u$ and $v$ are adjacent vertices. $u$ and $v$ are also known as neighbors. The set of neighbors of $v$, denoted $N(v)$, is called the neighborhood of $v$. The closed neighborhood of $v$ is $N[v]=N(v)\cup {v}$.

• If two edges share a vertex in common (e.g. $\{u,v\}$ and $\{v,w\})$, then they are adjacent edges.

• The degree of a vertex $v$, denoted deg($v$), is the number of vertices adjacent to $v$.

• We call $|V(G)|$, the cardinality of the vertices of a graph $G$, the order of the graph. We also say $|E(G)|$, the cardinality of the edges of a graph $G$, is the size of the graph.

• A graph of size 0 is called an empty graph. Any graph with at least one edge is called nonempty.

• A graph is complete when any two distinct vertices are adjacent. The complete graph of $n$ vertices is notated $K_{n}$

• A planar graph is a graph that can be embedded in the plane. I.e. it can be drawn on the plane such a way that its edges intersect only at their endpoints.

• A walk $W$ in a graph $G$ is a sequence of vertices in $G$, beginning at a vertex $u$ and ending at a vertex $v$ such that the consecutive vertices in $W$ are adjacent in $G$.

• A walk whose initial and terminal vertices are distinct is called an open walk, otherwise it is a closed walk.

• A walk in which no edge repeats is called a trail.

• A path $P$ in a graph $G$ is a sequence of edges which connect a sequence of vertices which, are all distinct from one another. A path can also be thought of as a walk with no repeated vertex.

• A simple path is one which contains no repeated vertices (in other words, it does not cross over itself).

• If there is a path from a vertex $u$ to a vertex $v$ then these two vertices are said to be connected. If every two vertices in a graph $G$ are connected, then $G$ is itself a connected graph.

• A nontrivial closed walk in a graph $G$ in which no edge is repeated is a circuit in $G$.

• A circuit with vertices $v_1, v_2, ..., v_k, v_1$ where $v_2, ..., v_k$ are all distinct is called a cycle.

• Let $G$ be a nontrivial connected graph. A circuit $C$ of $G$ that contains every edge of $G$ (necessarily exactly once) is called an Eularian Circuit. Any graph which contains an Eularian Circuit is called Eularian.

# 4. Properties

## 4.1. Subgraphs

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

• $V(H)\subseteq V(G)$

• $E(H)\subseteq E(G)$

$H$ is a proper subgraph if either

• $V(H)\subsetneq V(G)$

• $E(H)\subsetneq E(G)$

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

• G. Chartrand, L. Lesniak, and P. Zhang. Graphs and Digraphs. CRC Press, Oct. 2010.