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 K_{11} and K_{12} 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 a_{i} (i = 1, 2, . . . , m) in the disk Δ = S^{2}N(X;ℝ^{2}) where S^{2} = ℝ^{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 a_{i} (i = 1, 2, . . . , m) as a ℤ_{2}-basis. For any two arcs a_{i} and a_{j} with i ≠ j, the cross-index ɛ(a_{i}, a_{j}) is defined to be 0 or 1 according to whether the two boundary points ∂a_{j} of the arc a_{j} are in one component of the two open arcs ∂Δ∂a_{i} or not, respectively. For i = j, the identity ɛ(a_{i}, a_{j}) = 0 is taken. Then the cross-index ɛ(a_{i}, a_{j}) (mod 2) defines the symmetric bilinear ℤ_{2}-form
$$\varepsilon :{\mathbb{Z}}_{2}[D;X]\times {\mathbb{Z}}_{2}[D;X]\to {\mathbb{Z}}_{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 B_{i} (i = 1, 2, . . . , m) whose cores are the edges a_{i} (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 H_{1}(N(D;X); ℤ_{2}).
Because the nullity of the ℤ_{2}-intersection form on H_{1}(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))\ge 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 B_{i} (i = 1, 2, . . . , m) whose cores are the edges a_{i} (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 H_{1}(N(G); ℤ_{2}), which determines the genus g(N(G)) as the half of the ℤ_{2}-rank of ɛ. Thus, the inequalities
$$g(G;T)\le g(D;X)=g(N(G))\le 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 a_{i} (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
$$\nu (G;T)=1-\chi (G)-2g(G;T)=1-\chi (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
$$\varepsilon (D;X)=\sum _{1\le i<j\le m}\varepsilon ({a}_{i},{a}_{j}).$$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 a_{i} (i = 1, 2, . . . , m). Let ɛ_{ij} = ɛ(a_{i}, a_{j}) 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 a_{i}, we can find a sequence of integral pairs (i_{k}, j_{k}) (k = 1, 2, . . . , r) with 1 ≤ i_{1} < i_{2} · · · < i_{r} ≤ m and 1 ≤ j_{1} < j_{2} < · · · < j_{r} ≤ m such that ɛ_{ikjk} = 1 for all k (k = 1, 2, . . . , r). Here, note that this sequence (i_{k}, j_{k}) (k = 1, 2, . . . , r) may contain two pairs (i_{k}, j_{k}), (i_{k}_{′}, j_{k}_{′}) with k ≠ k′ and (i_{k}, j_{k}) = (j_{k}_{′}, i_{k}_{′}). By the identities ɛ_{ii} = 0 and ɛ_{ij} = ɛ_{ji} for all i, j, we have
$$2\varepsilon (D;X)=\sum _{1\le i,j\le m}{\varepsilon}_{ij}\ge \sum _{k=1}^{r}{\varepsilon}_{{i}_{k}{j}_{k}}=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 a_{i} (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 a_{i} into an embedded arc ${a}_{i}^{\prime}$ keeping the boundary points fixed, we construct a new based diagram (D′;X) of (G; T) with a basis ${a}_{i}^{\prime}(i=1,2,,\dots ,m)$ so that
(1) ${a}_{i}^{\prime}\cap {a}_{j}^{\prime}=\varnothing $ if ɛ(a_{i}, a_{j}) = 0 and i ≠ j,
(2) ${a}_{i}^{\prime}$ and ${a}_{j}^{\prime}$ meet one point transversely if ɛ(a_{i}, a_{j}) = 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 X_{i} (i = 1, 2, . . . , s) be all the tree basis diagrams of T in ℝ^{2}. For every i, let (D_{ij},X_{i}) (j = 1, 2, . . . , t_{i}) be a finite set of based diagrams of (G, T) such that every based diagram (D,X_{i}) of (G, T) coincides with a based diagram (D_{ij},X_{i}) for some j in a neighborhood of X_{i}. Then Calculation Lemma implies that the crossing number c(G; T) is equal to the minimum of the cross-indexes ɛ(D_{ij} ;X_{i}) 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
$$\varepsilon (G;T)=c(G;T)\ge c(G)\ge 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 S^{2} with c(D) = c(G). Put an upper arc around every crossing of D on a tube attaching to S^{2} 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 c^{T} (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 c^{T} (G) = ∞. The T-cross-index c^{T} (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 c^{T} (G) of a connected graph G for all trees T. The minimal value c^{min}(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 c^{max}(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
$${c}^{\text{max}}(G)\ge {c}^{\text{min}}(G)\ge c(G)\ge g(G)$$for every connected graph G. By definition, the following properties are mutually equivalent:
(i) G is a planar graph.
(ii) c^{max}(G) = 0.
(iii) c^{min}(G) = 0.
(iv) c(G) = 0.
(v) g(G) = 0.