<> Definition & Example ==================== - A (finite, undirected, simple) **graph** $G = (V,E)$ consists of a finite set $V$ of vertices and a set $E \subseteq \binom{V}{2}$ of edges. - Two graphs $G = (V,E)$ and $G = (V',E')$ are **isomorphic** if there is a bijection $\psi : V \rightarrow V'$ such that $$\{u,v\} \in E \Leftrightarrow \{\psi(u),\psi(v)\} \in E'.$$ - **Unlabelled graphs** on $n$ vertices are graphs up to graph-isomorphism. - A **canonical form** of an unlabelled graph is a relabelling of the vertices (an isomorphic graph) such that any two graphs are isomorphic if and only if they have the same canonical form. <> - Unlabelled graphs are graphically represented by their unlabelled vertices with edges connecting adjacent vertices. - For the number of unlabelled graphs see [OEIS:A000088](https://oeis.org/A000088). 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 **Eulerian Circuit**. Any graph which contains an Eularian Circuit is called **Eularian**. A graph is Eulerian if and only if all its vertices have even degrees. A nontrivial connected graph $G$ is Eularian if and only if every vertex of G has even degree. - Every planar graph is four-colorable. That is, the chromatic number of a planar graph is at most four. References ========== <> - [wikipedia](https://en.wikipedia.org/wiki/Graph_%28mathematics%29) - G. Chartrand, L. Lesniak, and P. Zhang. *Graphs and Digraphs.* CRC Press, Oct. 2010. Sage examples ============= {{{#!sagecell for n in [1,2,3,4]: Gs = graphs(n) print n, len(Gs) for P in graphs(3): print (sorted(P.edges(labels=False)),P.cardinality()) }}} Technical information for database usage ======================================== - A graph is uniquely represented as a tuple `(E,n)` where `E` is the sorted list of edges in the canonical labelling and `n` is the number of vertices. - Graphs are graded by the number of vertices. - The database contains all graphs of size at most 7.