Chapter 1 

Notation of Knots and Links

1.1  Basic graph theory

A graph G consists of a set V(G) of vertices and a set E(G) of edges, such that each edge is incident with two (not necessarily distinct) vertices. The edge is then said to join these two vertices, which are called the endpoints of the edge, and are said to be adjacent. Two edges are adjacent if they have a common endpoint. An edge which joins a vertex to itself is called a loop, while k edges which join the same pair of vertices are called k-multiple edges, and the corresponding graph is called a multigraph. If a multigraph contains only single and 2-multiple (or double) edges, it is called a 2-graph. A graph without multiple edges and loops is called a simple graph. A graph without loops is called a proper, or reduced graph.

If we distinguish the endpoints of edges, treating them as ordered pairs of vertices, we obtain oriented graphs (or digraphs).

A graph is usually drawn with enlarged (labelled) dots for the vertices, and straight lines (or sometimes curves) for edges in such a way that a vertex and an edge are incident iff they meet in the diagram. The actual placement of points in the diagram, and whether the lines representing edges are straight, curved or have to cross one another in any point other then vertex, is irrelevant.

The valence (or degree) of a vertex is the number of edges which are incident to it. (In a graph with loops, we usually count a loop-edge twice). The valence of a vertex v will be denoted d(v).

A vertex of a graph G is single or isolated if its valence is 0. Usually, a non-oriented graph without isolated vertices will be given by the list of unordered pairs representing edges. In the case of digraphs, ordered pairs will represent oriented edges. A graph can also be given by its adjacency matrix: a list where in every part the first datum is a vertex followed by the sequence of vertices adjacent to it, where the order of adjacent vertices is irrelevant.

A graph in which all vertices are k-valent will be called a k-valent graph (or k-regular graph). A graph containing only 3- and 4-valent vertices is called (3,4)-valent graph. In considering shadows and projections of KLs, 4-valent graphs will play the main role.

Among the graphs corresponding to the five Platonic regular polyhedra, the tetrahedron, cube and dodecahedron graphs are 3-valent, the octahedron graph is 4-valent, and the icosahedron graph is 5-valent.