  In this chapter (Chapter V) we present several results which demonstrate a
close connection and useful exchange of ideas between graph theory and knot
theory. These disciplines were shown to be related from the time of Tait (if
not Listing) but the great flow of ideas started only after Jones discoveries.
The first deep relation in this new trend was demonstrated by Morwen
Thistlethwaite and we describe several results by him in this Chapter. We also
presentresults from two (unpublished) preprints [P-P-0,P-18].In particular, in
Section 2, we sketch two generalizations of the Tutte polynomial of graphs or,
more precisely, the deletion-contraction method which Tutte polynomial utilize.
The first generalization considers, instead of graphs, general objects called
setoids or group systems. The second one deals with completion of the expansion
of a graph with respect to subgraphs. We are motivated here by finite type
invariants of links developed by Vassiliev and Gusarov along the line presented
in [P-9] (compare Chapter IX). The dichromatic Hopf algebra, described in
Section 2, have its origin in Vassiliev-Gusarov theory mixed with work of G.
Carlo-Rota and W. Schmitt. In Section 3 we describe Tait conjecture on
alternating link diagrams and apply developed methods to study adequate
diagrams. In Section 4 we apply 2-variable Kauffman polynomial to alternating
links and prove, in particular, the second Tait conjecture. In Section 5 we
analyze the Kauffman polynomial of adequate diagrams. In Section 6 we show how
coefficients of Homflypt polynomial can be used to obtain new information on
classical knot invariants (e.g. Morton-Franks-Williams inequality). In the last
section of Chapter V we discuss almost positive links and our method uses K.
Taniyama idea of ordering of knots.
