Graph

Graphs are abstract objects used in many areas of mathematics. Graphs are used to represent some idea of connectivity between elements. There is no singular definition for graph but rather different classes of graphs which are used for different purposes. Graphs are a useful abstraction and different kinds of graphs show up in several places in relation to polytopes.

Definitions

There is no singular definition for graph but rather different classes of graphs which are used for different purposes. Many of these definitions can be mixed with eachother

Simple graphs

The most basic kind of graph is a simple graph. A simple graph is a set of vertices V  and a set of edges ${\displaystyle E}$ consisting of unordered pairs of vertices. Traditionally edges in a simple graph cannot be self-loops, that is pairs where both vertices are equal are not permitted.

Graph diagrams

Graphs are often drawn as diagrams, by plotting the vertices as points and edges as curves with endpoints at the vertices it is incident on. Edges are permitted to cross each other, but graphs that can be drawn without crossing edges are called planar graphs and are of particular interest.

Multigraphs

A multigraph is an extension of simple graphs that allow for multiple edges between the same two vertices. Multigraphs are often considered to allow self loops as well.

Directed graphs

A directed graph is a type of graph where edges have direction. This means that edges are ordered pairs of vertices, with ${\displaystyle (v_{1},v_{2})}$ being a distinct edge from ${\displaystyle (v_{2},v_{1})}$. As with multigraphs direct graphs may or may not allow self loops depending on the author and the context. Directed multigraphs are multigraphs with directed edges.

The edges of a directed graph are usually drawn with an arrowhead on one end of the curve to indicate the direction. Sometimes an arrow head is placed on both sides of a curve to indicate that there are edges going both ways between two vertices.

Labeled graphs

Labled graphs are graphs which have labels assigned to their elements. They can be either a vertex labeled graph which has a function from the vertices of the graph to a label set or an edge labeled graph which has a function from the edges of the graph to a label set.

Coxeter diagrams are an example of labeled graphs in the study of polytopes. The Coxeter diagram of a Coxeter group is a simple graph whose edges are labeled with integers. The Coxeter diagram of a polytope also labels vertices, with ringed nodes, holes, etc.

Classes of graphs

With the above definitions it is often useful to talk about specific classes of graphs satisfying some property.

Regular graphs

A graph is regular if all of its vertices have the same degree. Note that this definition is not analygous to the definition of a regular polytope. Regularity is a local property of graphs and Regular graphs are not required to have any sort of transitive symmetry. The concept of a regular graph can be applied to simple graphs, multigraphs and even directed graphs.

An n -regular graph is a graph where all vertices have degree n . For example the skeleton of a polygon is always a 2 -regular graph.

A 3 -regular graphs is sometimes called a cubical graph.

Connected graphs

A connected graph is a graph where you can get from any vertex to any other vertex only by crossing edges. In a directed graph it is typically required that the connections go in the direction of the edges.

Colored graphs

Colored graphs are a special type of labeled graph. They are labeled with arbitrary values, often positive integers, called colors. Two adjacent elements (either edges or vertices depending on whether it is edge colored or vertex colored) cannot share the same color.

A coloring of a graph G  is a colored graph which is isomorphic to G  with its colors removed. A n -colorable graph is a graph for which a coloring exists using at most n  colors.

Vertex colored graphs

Vertex colored graphs are graphs whose vertices are labeled with colors, such that no two vertices of the same color are adjacent.

An important result on vertex colored graphs is the Four color theorem, which states that every planar graph has a coloring with 4 colors.

Edge colored graphs

Edge colored graphs are graphs whose edges are labeled with colors, such that no two edges of the same color are adjacent.[1] A graph is n -edge colorable if there is a coloring of that graph which uses n  colors and the edge chromatic number of a graph is the smallest n  such that it is n -edge colorable.[1]

Edge colored graphs are used in the study of both colorful polytopes and flag graphs.

Properly edge colored graphs

A properly edge colored graph is an edge colored graph is an n -edge colored graph which is also n -regular.[2][1]

Graph isomorphisms

An isomorphism between graphs ${\displaystyle G_{1}=(V_{1},E_{1})}$ and ${\displaystyle G_{2}=(V_{2},E_{2})}$ is a bijection ${\displaystyle \varphi :V_{1}\rightarrow V_{2}}$ and a bijection ${\displaystyle \psi :E_{1}\rightarrow E_{2}}$ such that ${\displaystyle v:V_{1}}$ is incident on ${\displaystyle e:E_{1}}$ iff ${\displaystyle \varphi (v)}$ is incident on ${\displaystyle \psi (e)}$. That is to say it is a mapping between vertices that preserves adjacency.

An isomorphism φ , ψ  between edge colored graphs G1  and G2  is color respecting iff for any two edges of the same color e1  and e2 , ${\displaystyle \psi (e_{1})}$ is the same color as ${\displaystyle \psi (e_{2})}$.[3] A color respecting isomorphism is color preserving iff for any edge e  in G1 , e  is the same color as ${\displaystyle \psi (e)}$.[3]

A graph automorphism is an isomorphism from a graph to itself.