By a graph, a connected graph G with only topological edges and without vertexes of degrees 0, 1 and 2 is meant. Let G have n(≥ 1) vertexes and s(≥ 1) edges. By definition, if n = 1 (that is, G is a bouquet of loops), then every tree basis T of G has one vertex. A diagram of a graph G is a representation D of G in the plane so that the vertexes of G are represented by distinct points and the edges of G are represented by arcs joining the vertexes which may have transversely meeting double points avoiding the vertexes. A double point on the edges of a diagram D is called a crossing of D. In this paper, to distinguish between a degree 4 vertex and a crossing, a crossing is denoted by a crossing with over-under information except in Figs. 7, 8 representing diagrams of the graphs K11 and K12 without degree 4 vertexes. A tree diagram of a tree T is a diagram X of T without crossings. A based diagram of a based graph (G; T) is a pair (D;X) where D is a diagram of G and X is a sub-diagram of D such that X is a tree diagram of the tree basis T without crossings in D. In this case, the diagram X is called a tree basis diagram. The following lemma is used without proof in the author’s earlier papers [3, 4].
Lemma 2.1
Given any based graph (G; T) in ℝ3, then every spatial graph diagram of G is transformed into a based diagram (D;X) of (G; T) only with crossings with over-under information by the Reidemeister moves I–V (see Fig. 1).
ProofIn any spatial graph diagram D′ of G, first transform the sub-diagram D(T) of the tree basis T in D′ into a tree diagram X by the Reidemeister moves I–V. Since a regular neighborhood N(X;ℝ2) of X in the plane ℝ2 is a disk, a based diagram is obtained by shrinking this tree diagram into a very small tree diagram within the disk by the Reidemeister moves I–V. See Fig. 2 for this transformation. Thus, we have a based diagram (D;X) of (G; T) only with crossings with over-under information.
The crossing number c(D) of a based diagram (D;X) is denoted by c(D;X). The crossing number c(G; T) of a based graph (G; T) is the minimal number of the crossing numbers c(D;X) of all based diagrams (D;X) of (G; T). For a based diagram (D;X) of (G; T), let N(X;D) = D ∩N(X;ℝ2) be a regular neighborhood of X in the diagram D. Then the complement cl(DN(X;D)) is a tangle diagram of m-strings ai (i = 1, 2, . . . , m) in the disk Δ = S2N(X;ℝ2) where S2 = ℝ2∪{∞} denotes the 2-sphere which is the one-point compactification of the plane ℝ2.
Let ℤ2[D;X] be the ℤ2 vector space with the arcs ai (i = 1, 2, . . . , m) as a ℤ2-basis. For any two arcs ai and aj with i ≠ j, the cross-index ɛ(ai, aj) is defined to be 0 or 1 according to whether the two boundary points ∂aj of the arc aj are in one component of the two open arcs ∂Δ∂ai or not, respectively. For i = j, the identity ɛ(ai, aj) = 0 is taken. Then the cross-index ɛ(ai, aj) (mod 2) defines the symmetric bilinear ℤ2-form
ɛ:ℤ2[D;X]×ℤ2[D;X]→ℤ2,called the ℤ2-form on (D;X). The genus g(D;X) of the based diagram (D;X) is defined to be half of the ℤ2-rank of the ℤ2-form ɛ : ℤ2[D;X] × ℤ2[D;X] → ℤ2, which is seen to be even since the ℤ2-form ɛ is a ℤ2-symplectic form.
The genus g(G; T) of a based graph (G; T) is the minimum of the genus g(D;X) for all based diagrams (D;X) of (G; T). The following lemma shows that the genus g(G) of a graph G is calculable from based diagrams (D;X) of any based graph (G; T) of G.
Lemma 2.2
(Genus Lemma) g(G) = g(D;X) = g(G; T) for any based diagram (D;X) of any based graph (G, T).
ProofLet (D;X) be a based diagram of a based graph (G; T) with g(D;X) = g(G; T). Constructs a compact connected orientable surface N(D;X) from (D;X) such that
(1) the surface N(D;X) is a union of a disk N in ℝ2 with the tree basis diagram X as a spine and attaching bands Bi (i = 1, 2, . . . , m) whose cores are the edges ai (i = 1, 2, . . . , m) of D,
(2) the ℤ2-form ɛ : ℤ2[D;X]×ℤ2[D;X] → ℤ2 is isomorphic to the ℤ2-intersection form on H1(N(D;X); ℤ2).
Because the nullity of the ℤ2-intersection form on H1(N(D;X); ℤ2) is equal to the number of the boundary components of the bounded surface N(D;X) minus one, the genus g(N(D;X)) is equal to the half of the ℤ2-rank of the ℤ2-form ɛ. This implies that
g(G;T)=g(D;X)=g(N(D;X))≥g(G).Conversely, let F be a compact connected orientable surface containing G with genus g(F) = g(G), where F need not be closed. For any based graph (G; T), let N(G) be a regular neighborhood of G in F, which is obtained from a disk N in F with the tree basis T as a spine by attaching bands Bi (i = 1, 2, . . . , m) whose cores are the edges ai (i = 1, 2, . . . , m) of G. Then the inequality g(N(G)) ≤ g(F) holds. Let (D;X) be any based diagram of the based graph (G; T). Identify the disk N with a disk N(X) with the tree basis T as a spine. By construction, the ℤ2-form ɛ : ℤ2[D;X]×ℤ2[D;X] → ℤ2 is isomorphic to the ℤ2-intersection form on H1(N(G); ℤ2), which determines the genus g(N(G)) as the half of the ℤ2-rank of ɛ. Thus, the inequalities
g(G;T)≤g(D;X)=g(N(G))≤g(F)=g(G)hold and we have g(G) = g(D; T) = g(G; T) for any based diagram (D;X) of (G; T).
The nullity ν(D;X) of (D;X) is the nullity of the ℤ2-form ɛ : ℤ2[D;X] × ℤ2[D;X] → ℤ2. The nullity ν(G; T) of a based graph (G; T) is the maximum of the nullity ν(D;X) for all based diagrams (D;X) of (G; T). Then the following corollary is obtained:
Corollary 2.3
The identity ν(G; T) = 1−χ(G)−2g(G) holds for any based graph (G, T).
This corollary shows that the nullity ν(G; T) is independent of a choice of tree bases T of G, and is therefore simply called the nullity of G and denoted by ν(G).
ProofThe graph G is obtained from the tree graph N(X;D) by attaching the mutually disjoint m-strings ai (i = 1, 2, . . . , m). Since the ℤ2-rank of ℤ2[D;X] is m by definition, we see from a calculation of the Euler characteristic χ(G) that χ(G) = 1+m−2m = 1−m. By the identity m = 2g(D;X)+ν(D;X) on the rank and the nullity of the ℤ2-form ɛ, the nullity ν(D;X) of a based diagram (D;X) of (G; T) is given by ν(D;X) = m−2g(D;X) = 1−χ(G) −2g(D;X). Hence we have
ν(G;T)=1-χ(G)-2g(G;T)=1-χ(G)-2g(G)by Lemma 2.2.
The cross-index of a based diagram (D;X) is the non-negative integer ɛ(D;X) defined by
ɛ(D;X)=∑1≤i<j≤mɛ(ai,aj).The following lemma is obtained:
Lemma 2.4
For every based diagram (D;X), the inequality ɛ(D;X) ≥ g(D;X) holds.
ProofLet V be the ℤ2-matrix representing the ℤ2-form ɛ : ℤ2[D;X]×ℤ2[D;X] → ℤ2 with respect to the arc basis ai (i = 1, 2, . . . , m). Let ɛij = ɛ(ai, aj) be the (i, j)-entry of the matrix V. The ℤ2-rank r of the matrix V is equal to 2g(D;X) by definition. There are r column vectors in V that are ℤ2-linearly independent. By changing the indexes of the arc basis ai, we can find a sequence of integral pairs (ik, jk) (k = 1, 2, . . . , r) with 1 ≤ i1 < i2 · · · < ir ≤ m and 1 ≤ j1 < j2 < · · · < jr ≤ m such that ɛikjk = 1 for all k (k = 1, 2, . . . , r). Here, note that this sequence (ik, jk) (k = 1, 2, . . . , r) may contain two pairs (ik, jk), (ik′, jk′) with k ≠ k′ and (ik, jk) = (jk′, ik′). By the identities ɛii = 0 and ɛij = ɛji for all i, j, we have
2ɛ(D;X)=∑1≤i,j≤mɛij≥∑k=1rɛikjk=r=2g(D;X).Thus, the inequality ɛ(D;X) ≥ g(D;X) is obtained.
The cross-index ɛ(G; T) of a based graph (G; T) is the minimum of the cross-index ɛ(D;X) for all based diagrams (D;X) of (G; T). It may be used to compute the crossing number c(G; T) of a based graph (G; T) as it is stated in the following lemma:
Lemma 2.5
(Calculation Lemma) ɛ(G; T) = c(G; T) for every based graph (G; T).
ProofLet ai (i = 1, 2, . . . , m) be an arc basis of a based diagram (D;X) of (G; T) attaching to the boundary of a regular neighborhood disk N of X in the plane.
By a homotopic deformation of ai into an embedded arc ai′ keeping the boundary points fixed, we construct a new based diagram (D′;X) of (G; T) with a basis ai′(i=1,2,,…,m) so that
(1) ai′∩aj′=∅ if ɛ(ai, aj) = 0 and i ≠ j,
(2) ai′ and aj′ meet one point transversely if ɛ(ai, aj) = 1.
Then the cross-index ɛ(D;X) is equal to the crossing number c(D′;X) of the based diagram (D′;X) of (G; T). Hence the inequality ɛ(G; T) ≥ c(G; T) is obtained. Since ɛ(D;X) ≤ c(D;X) for every based graph (D;X) of (G; T), the inequality ɛ(G; T) ≤ c(G; T) holds. Hence the identity ɛ(G; T) = c(G; T) holds.
Calculation Lemma (Lemma 2.5) gives a computation method of the crossing number c(G; T) of a based graph (G; T) in a finite procedure.
In fact, let Xi (i = 1, 2, . . . , s) be all the tree basis diagrams of T in ℝ2. For every i, let (Dij,Xi) (j = 1, 2, . . . , ti) be a finite set of based diagrams of (G, T) such that every based diagram (D,Xi) of (G, T) coincides with a based diagram (Dij,Xi) for some j in a neighborhood of Xi. Then Calculation Lemma implies that the crossing number c(G; T) is equal to the minimum of the cross-indexes ɛ(Dij ;Xi) for all i, j.
The following corollary is obtained by a combination of Lemmas 2.2, 2.5 and definition and some observation.
Corollary 2.6
The inequalities
ɛ(G;T)=c(G;T)≥c(G)≥g(G)=g(G;T)hold for every based graph (G; T).
ProofThe identity ɛ(G; T) = c(G; T) is given by Lemma 2.5. By definition, the inequality c(G; T) ≥ c(G) is given. To see that c(G) ≥ g(G), let D be a diagram of G with over-under information on the sphere S2 with c(D) = c(G). Put an upper arc around every crossing of D on a tube attaching to S2 to obtain a closed orientable surface of genus c(D) with G embedded (see Fig. 3).
Hence the inequality c(G) ≥ g(G) is obtained. The identity g(G) = g(G; T) is given by Lemma 2.2. (Incidentally, the inequality c(G; T) ≥ g(G; T) is directly obtained by Lemma 2.4.)
For an arbitrary tree T, the T-cross-index cT (G) of a connected graph G is the minimal number of c(G; T′) for all tree bases T′ of G such that T′ is homeomorphic to T if such a tree basis T′ of G exists. Otherwise, let cT (G) = ∞. The T-cross-index cT (G) is a topological invariant of a graph G associated to every tree T, whose computation is in principle simpler than a computation of the crossing number c(G) by Calculation Lemma (Lemma 2.5).
Let c*(G) be the family of the invariants cT (G) of a connected graph G for all trees T. The minimal value cmin(G) in the family c*(G) has appeared as the crossing number of a Γ-unknotted graph in the paper [3] on a spatial graph.
The finite maximal value cmax(G) in the family c*(G) is a well-defined invariant of a connected graph G, because there are only finitely many tree bases T in G. By definition, we have the following inequalities
cmax(G)≥cmin(G)≥c(G)≥g(G)for every connected graph G. By definition, the following properties are mutually equivalent:
(i) G is a planar graph.
(ii) cmax(G) = 0.
(iii) cmin(G) = 0.
(iv) c(G) = 0.
(v) g(G) = 0.