Graphs (undirected, unlabelled, and simple)

# 1. Definition

A 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 104 statistics in the database:

The number of edges of a graph.
The number of subgraphs.
The number of induced subgraphs.
The length of the maximal independent set of vertices of a graph.
The number of triangles of a graph.
The number of spanning trees of a graph.
The order of the largest clique of the graph.
The chromatic number of a graph.
The degree of the graph.
The Grundy number of a graph.
The cardinality of the automorphism group of a graph.
The burning number of a graph.
The diameter of a connected graph.
The radius of a connected graph.
The edge connectivity of a graph.
The vertex connectivity of a graph.
The Szeged index of a graph.
The girth of a graph, which is not a tree.
The Wiener index of a graph.
The number of spanning subgraphs of a graph with the same connected components.
The number of maximal spanning forests contained in a graph.
The number of strongly connected orientations of a graph.
The number of acyclic orientations of a graph.
The number of forests contained in a graph.
The chromatic index of a connected graph.
The treewidth of a graph.
The domination number of a graph.
The number of perfect matchings of a graph.
The size of the preimage of the map 'to graph' from Ordered trees to Graphs.
The size of the preimage of the map 'to graph' from Binary trees to Graphs.
The number of connected components of the complement of a graph.
The number of connected components of a graph.
The number of nonisomorphic vertex-induced subtrees.
The number of independent sets of vertices of a graph.
The number of facets of the stable set polytope of a graph.
The determinant of the distance matrix of a connected graph.
The determinant of the product of the incidence matrix and its transpose of a gra....
The number of vertices with even degree.
The minimal degree of a vertex of a graph.
The number of vertices of odd degree in a graph.
The number of leaves in a graph.
The number of degree 2 vertices of a graph.
The number of isolated vertices of a graph.
The skewness of a graph.
The minimal crossing number of a graph.
The number of spanning subgraphs of a graph.
The number of strongly connected outdegree sequences of a graph.
The number of different adjacency matrices of a graph.
The sum of the vertex degrees of a graph.
The determinant of the adjacency matrix of a graph.
The second Zagreb index of a graph.
The size of a minimal vertex cover of a graph.
The number of minimal vertex covers of a graph.
The exponent of the automorphism group of a graph.
The Altshuler-Steinberg determinant of a graph.
The genus of a graph.
The number of Hamiltonian cycles in a graph.
The matching number of a graph.
The number of orbits of vertices of a graph under automorphisms.
The Szeged index minus the Wiener index of a graph.
The energy of a graph, if it is integral.
The number of pairs of vertices of a graph with distance 3.
The number of pairs of vertices of a graph with distance 2.
The number of pairs of vertices of a graph with distance 4.
The number of edges minus the number of vertices plus 2 of a graph.
The number of distinct eigenvalues of a graph.
The number of distinct Laplacian eigenvalues of a graph.
The largest eigenvalue of a graph if it is integral.
The second largest eigenvalue of a graph if it is integral.
The monochromatic index of a connected graph.
The Schultz index of a connected graph.
The first Zagreb index of a graph.
The Gutman (or modified Schultz) index of a connected graph.
The hyper-Wiener index of a connected graph.
The Hosoya index of a graph.
The distinguishing number of a graph.
The Ramsey number of a graph.
The (zero)-forcing number of a graph.
The rank-width of a graph.
The pathwidth of a graph.
The cutwidth of a graph.
The cop number of a graph.
The number of cut vertices of a graph.
The number of blocks of a connected graph.
The F-index (or forgotten topological index) of a graph.
The hull number of a graph.
The length of the longest cycle in a graph.
The maximin edge-connectivity for choosing a subgraph.
The toughness times the least common multiple of 1,.
The largest Laplacian eigenvalue of a graph if it is integral.
The number of different neighbourhoods in a graph.
The maximal cardinality of a set of vertices with the same neighbourhood in a gra....
The Colin de VerdiÃ¨re graph invariant.
The largest multiplicity of a distance Laplacian eigenvalue in a connected graph.....
The multiplicity of the largest distance Laplacian eigenvalue in a connected grap....
The multiplicity of the largest Laplacian eigenvalue in a graph.
The maximal multiplicity of a Laplacian eigenvalue in a graph.
The multiplicity of the largest eigenvalue in a graph.
The maximal multiplicity of an eigenvalue in a graph.
The number of distinct eigenvalues of the distance Laplacian of a connected graph....
The metric dimension of a graph.
The number of distinct colouring schemes of a graph.
The maximal number of occurrences of a colour in a proper colouring of a graph.
The Hadwiger number of the graph.

# 6. Maps

We have the following 3 maps in the database:

to partition of connected components
complement
Ore closure

# 7. References

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

# 8. Sage examples

Graphs (last edited 2016-05-30 11:33:50 by ChristianStump)