Search

We find a graph of genus $5$ and its drawing on the orientable surface of genus $4$ with every pair of independent edges crossing an even number of times. This shows that the strong Hanani-Tutte theorem cannot be extended to the orientable surface of genus $4$. As a base step in the construction we use a counterexample to an extension of the unified Hanani-Tutte theorem on the torus., 12 pages, 4 figures; minor revision, new section on open problems

A graph is planar if it has a drawing in which no two edges cross. The Hanani-Tutte Theorem states that a graph is planar if it has a drawing $D$ such that any two edges in $D$ cross an even number of times. A graph $G$ is a non-separating planar graph if it has a drawing $D$ such that (1) edges do not cross in $D$, and (2) for any cycle $C$ and any two vertices $u$ and $v$ that are not in $C$, $u$ and $v$ are on the same side of $C$ in $D$. Non-separating planar graphs are closed under taking minors and hence have a finite forbidden minor characterisation. In this paper, we prove a Hanani-Tutte type theorem for non-separating planar graphs. We use this theorem to prove a stronger version of the strong Hanani-Tutte Theorem for planar graphs, namely that a graph is planar if it has a drawing in which any two disjoint edges cross an even number of times or it has a chordless cycle that enables a suitable decomposition of the graph.

We introduce the notion of a delta-matroid perspective. A delta-matroid perspective consists of a triple ( M , D , N ) , where M and N are matroids and D is a delta-matroid such that there are strong maps from M to the upper matroid of D and from the lower matroid of D to N . We describe two Tutte-like polynomials that are naturally associated with delta-matroid perspectives and determine various properties of them. Furthermore, we show when the delta-matroid perspective is read from a graph in a surface our polynomials coincide with B. Bollobas and O. Riordan's ribbon graph polynomial and the more general Krushkal polynomial of graphs in surfaces. This is analogous to the fact that the Tutte polynomial of a graph G coincides with the Tutte polynomial of its cycle matroid. We use this new framework to prove results about the topological graph polynomials that cannot be realised in the setting of cellularly embedded graphs.

Self-similar graphs were widely studied in both combinatorics and statistical physics. Motivated by the construction of the well-known 3-dimensional Sierpinski gasket graphs, in this paper we introduce a family of recursively constructed self-similar graphs whose inner duals are of the self-similar property. By combining the dual property of the Tutte polynomial and the subgraph-decomposition trick, we show that the Tutte polynomial of this family of graphs can be computed in an iterative way and in particular the exact expression of the formula of the number of their spanning trees is derived. Furthermore, we show our method is a general one that is easily extended to compute Tutte polynomials for other families of self-similar graphs such as Farey graphs, 2-dimensional Sierpinski gasket graphs, Hanoi graphs, modified Koch graphs, Apollonian graphs, pseudofractal scale-free web, fractal scale-free network, etc.

Tutte–Grothendieck invariants of graphs are mappings from a class of graphs to a commutative ring that are characterized recursively by contraction-deletion rules. Well known examples are the Tutte, chromatic, tension and flow polynomials. Suppose that an edge cut C divides a graph G into two parts G1, G1′ and that G1, G1′ are the sets of minors of G whose edge sets consist of C and edges of G1, G1′, respectively. We study determinant formulas evaluating a Tutte–Grothendieck invariant of G from the Tutte–Grothendieck invariants of graphs from G1 and G1′.

We obtain a sharp result that for any even n ? 34, every {Dn,Dn+1}-regular graph of order n contains ?n/4? disjoint perfect matchings, where Dn = 2?n/4?-1. As a consequence, for any integer D ? Dn, every {D, D+1}- regular graph of order n contains (D-?n/4?+1) disjoint perfect matchings.

The Tutte polynomial of a graph, or equivalently the q-state Potts model partition function, is a two-variable polynomial graph invariant of considerable importance in both statistical physics and combinatorics. The computation of this invariant for a graph is NP-hard in general. In this paper, we focus on two iteratively growing scale-free networks, which are ubiquitous in real-life systems. Based on their self-similar structures, we mainly obtain recursive formulas for the Tutte polynomials of two scale-free networks (lattices), one is fractal and “large world”, while the other is non-fractal but possess the small-world property. Furthermore, we give some exact analytical expressions of the Tutte polynomial for several special points at (x, y)-plane, such as, the number of spanning trees, the number of acyclic orientations, etc.

Let $c_n$ denote the number of vertex-labeled connected graphs on $n$ vertices. Using group actions and elementary number theory, we show that the infinite sequence, $c_n : n \ge 1,$ is ultimately periodic modulo every positive integer. We state and prove our results for sequences defined by a weighted generalization of $c_n$ and conjecture that these results are suggestive of similar periodic behavior of the Tutte polynomial evaluations of the complete graph $K_n$ at integer points.

We establish a relation between the Bollobas–Riordan polynomial of a ribbon graph with the relative Tutte polynomial of a plane graph obtained from the ribbon graph using its projection to the plane in a nontrivial way. Also we give a duality formula for the relative Tutte polynomial of dual plane graphs and an expression of the Kauffman bracket of a virtual link as a specialization of the relative Tutte polynomial.

Using two related parameters, ζ and γ, we extend the recursion for com- puting the Tutte polynomial of any graph to the computation of the Tutte polynomial of any multigraph. With this recursion, we found explicit formulae for several fami- lies of multigraphs. In particular, the Tutte polynomials of some cyclic multigraphs, 2−tree multigraphs, and any l−bridge multigraph.

We introduce a common generalization of the strong Hanani–Tutte theorem and the weak Hanani–Tutte theorem: if a graph $G$ has a drawing $D$ in the plane where every pair of independent edges crosses an even number of times, then $G$ has a planar drawing preserving the rotation of each vertex whose incident edges cross each other evenly in $D$. The theorem is implicit in the proof of the strong Hanani–Tutte theorem by Pelsmajer, Schaefer and Štefankovič. We give a new, somewhat simpler proof.

We describe an algorithm to compute the Tutte polynomial of large fragments of Archimedean tilings by squares, triangles, hexagons and combinations thereof. Our algorithm improves a well known method for computing the Tutte polynomial of square lattices. We also address the problem of obtaining Tutte polynomial evaluations from the symbolic expressions generated by our algorithm, improving the best known lower bound for the asymptotics of the number of spanning forests, and the lower and upper bounds for the asymptotics of the number of acyclic orientations of the square lattice.

We introduce an arithmetic version of the multivariate Tutte polynomial recently studied by Sokal, and a quasi-polynomial that interpolates between the two. We provide a generalized Fortuin-Kasteleyn representation for representable arithmetic matroids, with applications to arithmetic colorings and flows. We give a new proof of the positivity of the coefficients of the arithmetic Tutte polynomial in the more general framework of pseudo-arithmetic matroids. In the case of a representable arithmetic matroid, we provide a geometric interpretation of the coefficients of the arithmetic Tutte polynomial., Nous introduisons une version arithmétique du polynôme de Tutte multivariée récemment étudié par Sokal, et un quasi-polynôme qui interpole entre les deux. Nous proposons une représentation de Fortuin-Kasteleyn neutralise pour les matroïdes arithmétiques représentables, avec des applications aux colorations et flux arithmétiques. Nous donnons une nouvelle preuve de la positivité des coefficients du polynôme de Tutte arithmétique dans le cadre plus général des matroïdes pseudo-arithmétiques. Dans le cas d'un matroïde arithmétique représentable, nous proposons une interprétation géométrique des coefficients du polynôme de Tutte arithmétique.

A graph G with a perfect matching is called saturated if G + e has more perfect matchings than G for any edge e that is not in G. Lovasz gave a characterization of the saturated graphs called the cathedral theorem, with some applications to the enumeration problem of perfect matchings, and later Szigeti gave another proof. In this paper, we give a new proof with our preceding works which revealed canonical structures of general graphs with perfect matchings. Here, the cathedral theorem is derived in quite a natural way, providing more refined or generalized properties. Moreover, the new proof shows that it can be proved without using the Gallai-Edmonds structure theorem.

Cayley polytopes were defined recently as convex hulls of Cayley compositions introduced by Cayley in 1857. In this paper we resolve Braun's conjecture, which expresses the volume of Cayley polytopes in terms of the number of connected graphs. We extend this result to two one-variable deformations of Cayley polytopes (which we call t-Cayley and t-Gayley polytopes), and to the most general two-variable deformations, which we call Tutte polytopes. The volume of the latter is given via an evaluation of the Tutte polynomial of the complete graph. Our approach is based on an explicit triangulation of the Cayley and Tutte polytope. We prove that simplices in the triangulations correspond to labeled trees. The heart of the proof is a direct bijection based on the neighbors-first search graph traversal algorithm., 32 pages, 11 figures

In this paper we recursively describe the Tutte polynomial of an infinite family of outerplanar, small-world and self-similar graphs. In particular, we study the Abelian Sandpile Model on these graphs and obtain the generating function of the recurrent configurations. Further, we give some exact analytical expression for the Tutte polynomial at several special points

A graph G has a perfect matching if and only if 0 is not a root of its matching polynomial μ ( G , x ) . Thus, Tutte’s famous theorem asserts that 0 is not a root of μ ( G , x ) if and only if c odd ( G − S ) ≤ | S | for all S ⊆ V ( G ) , where c odd ( G ) denotes the number of odd components of G . Tutte’s theorem can be proved using a characterization of the structure of maximal non-matchable graphs, that is, the edge-maximal graphs among those having no perfect matching. In this paper, we prove a generalized version of Tutte’s theorem in terms of avoiding any given real number θ as a root of μ ( G , x ) . We also extend maximal non-matchable graphs to maximal θ -non-matchable graphs and determine the structure of such graphs.

A perfect matchingMin an edge-coloured complete bipartite graphKn,nis rainbow if no pair of edges inMhave the same colour. We obtain asymptotic enumeration results for the number of rainbow perfect matchings in terms of the maximum number of occurrences of each colour. We also consider two natural models of random edge-colourings ofKn,nand show that if the number of colours is at leastn, then there is with high probability a rainbow perfect matching. This in particular shows that almost every square matrix of ordernin which every entry appearsntimes has a Latin transversal.

We consider several classes of planar polycyclic graphs and derive the recurrences satisfied by their Tutte polynomials. The recurrences are then solved by computing the corresponding generating functions. As a consequence, we obtain values of several chemically and combinatorially interesting enumerative invariants of considered graphs. Some of them can be expressed in terms of values of Chebyshev polynomials of the second kind.

In this paper we show that, with 11 exceptions, any matching covered bipartite graph on $n$ vertices, with minimum degree greater than two, has at least $2n-4$ perfect matchings. Using this bound, which is the best possible, and McCuaig's theorem [W. McCuaig, J. Graph Theory, 38 (2001), pp. 124--169] on brace generation, we show that any brace on $n$ vertices has at least $(n-2)^2/8$ perfect matchings. A bi-wheel on $n$ vertices has $(n-2)^2/4$ perfect matchings. We conjecture that there exists an integer $N$ such that every brace on $n\geq N$ vertices has at least $(n-2)^2/4$ perfect matchings.

A gain graph is a graph whose edges are orientably labelled from a group. A weighted gain graph is a gain graph with vertex weights from an abelian semigroup, where the gain group is lattice ordered and acts on the weight semigroup. For weighted gain graphs we establish basic properties and we present general dichromatic and forest-expansion polynomials that are Tutte invariants (they satisfy Tutte's deletion-contraction and multiplicative identities). Our dichromatic polynomial includes the classical graph one by Tutte, Zaslavsky's two for gain graphs, Noble and Welsh's for graphs with positive integer weights, and that of rooted integral gain graphs by Forge and Zaslavsky. It is not a universal Tutte invariant of weighted gain graphs; that remains to be found. An evaluation of one example of our polynomial counts proper list colorations of the gain graph from a color set with a gain-group action. When the gain group is Z^d, the lists are order ideals in the integer lattice Z^d, and there are specified upper bounds on the colors, then there is a formula for the number of bounded proper colorations that is a piecewise polynomial function of the upper bounds, of degree nd where n is the order of the graph. This example leads to graph-theoretical formulas for the number of integer lattice points in an orthotope but outside a finite number of affinographic hyperplanes, and for the number of n x d integral matrices that lie between two specified matrices but not in any of certain subspaces defined by simple row equations., 32 pp. Submitted in 2007, extensive revisions in 2013 (!). V3: Added references, clarified examples. 35 pp

The perfect matchings in the n-cube have earlier been enumerated for n ≤ 6. A dynamic programming approach is here used to obtain the total number of perfect matchings in the 7-cube, which is 391 689 748 492 473 664 721 077 609 089. The number of equivalence classes of perfect matchings is further shown to be 336 in the 5-cube, 356 788 059 in the 6-cube and 607 158 046 495 120 886 820 621 in the 7-cube. The techniques used can be generalized to arbitrary bipartite and general graphs.

In this paper, we generalize the notions of perfect matchings, perfect 2-matchings to perfect k-matchings and give a necessary and sufficient condition for the existence of perfect k-matchings. We show that a bipartite graph G contains a perfect k-matching if and only if it contains a perfect matching. Moreover, for regular graphs, we provide a sufficient condition for the existence of perfect k-matching in terms of the edge connectivity.

Triesch (1997) [25] conjectured that Hall’s classical theorem on matchings in bipartite graphs is a special case of a phenomenon of monotonicity for the number of matchings in such graphs. We prove this conjecture for all graphs with sufficiently many edges by deriving an explicit monotonic formula counting matchings in bipartite graphs.This formula follows from a general duality theory which we develop for counting matchings. Moreover, we make use of generating functions for set functions as introduced by Lass [20], and we show how they are useful for counting matchings in bipartite graphs in many different ways.

We introduce a new property of graphs called ‘q-state Potts unique-ness’ and relate it to chromatic and Tutte uniqueness, and also to ‘chromatic–flow uniqueness’, recently studied by Duan, Wu and Yu. We establish for which edge-weighted graphs H homomor-phism functions from multigraphs G to H are specializations of the Tutte polynomial of G, in particular answering a question of Freed-man, Lovász and Schrijver. We also determine for which edge-weighted graphs H homomorphism functions from multigraphs G to H are specializations of the ‘edge elimination polynomial’ of Averbouch, Godlin and Makowsky and the ‘induced subgraph poly-nomial’ of Tittmann, Averbouch and Makowsky. Unifying the study of these and related problems is the notion of the left and right homomorphism profiles of a graph. Ministerio de Educación y Ciencia MTM2008-05866-C03-01 Junta de Andalucía FQM- 0164 Junta de Andalucía P06-FQM-01649

We provide a new proof of Brylawski’s formula for the Tutte polynomial of the tensor product of two matroids. Our proof involves extending Tutte’s formula, expressing the Tutte polynomial using a calculus of activities, to all polynomials involved in Brylawski’s formula. The approach presented here may be used to show a signed generalization of Brylawski’s formula, which may be used to compute the Jones polynomial of some large non-alternating knots. Our proof inspires an extension of Brylawski’s formula to the case when the pointed element is a factor.

In [A polynomial invariant of graphs on orientable surfaces, Proc. Lond. Math. Soc., III Ser. 83, No. 3, 513-531 (2001)] and [A polynomial of graphs on surfaces, Math. Ann. 323, 81-96 (2002)], Bollobas and Riordan generalized the classical Tutte polynomial to graphs cellularly embedded in surfaces, i.e. ribbon graphs, thus encoding topological information not captured by the classical Tutte polynomial. We provide a `recipe theorem' for their new topological Tutte polynomial, R(G). We then relate R(G) to the generalized transition polynomial Q(G) via a medial graph construction, thus extending the relation between the classical Tutte polynomial and the Martin, or circuit partition, polynomial to ribbon graphs. We use this relation to prove a duality property for R(G) that holds for both oriented and unoriented ribbon graphs. We conclude by placing the results of Chumutov and Pak [The Kauffman bracket and the Bollobas-Riordan polynomial of ribbon graphs, Moscow Mathematical Journal 7(3) (2007) 409-418] for virtual links in the context of the relation between R(G) and Q(R)., Comment: 23 pages, 10 figures, dedicated to Thomas Brylawski

We give a general convolution–multiplication identity for the multivariate and bivariate rank generating polynomial of a graph or matroid. The bivariate rank generating polynomial is transformable to and from the Tutte polynomial by simple algebraic operations. Several identities, almost all already known in some form, are specializations of this identity. Combinatorial or probabilistic interpretations are given for the specialized identities.

In order to facilitate recognition of polymer graphs and patterns obtained by graphical recombination, we analyze polynomial invariants, graphs and knots associated to polyominoes, polyiamonds, and polyhexes.

We show that the problem of approximately evaluating the Tutte polynomial of triangular graphs at the points (q, 1/q) of the Tutte plane is BQP-complete for (most) roots of unity q. We also consider circular graphs and show that the problem of approximately evaluating the Tutte polynomial of these graphs at the point (e2πi/5, e-2πi/5) is DQC1-complete and at points [Formula: see text] for some integer k is in BQP. To show that these problems can be solved by a quantum computer, we rely on the relation of the Tutte polynomial of a planar G graph with the Jones and HOMFLY polynomial of the alternating link D(G) given by the medial graph of G. In the case of our graphs the corresponding links are equal to the plat and trace closures of braids. It is known how to evaluate the Jones and HOMFLY polynomial for closures of braids. To establish the hardness results, we use the property that the images of the generators of the braid group under the irreducible Jones–Wenzl representations of the Hecke algebra have finite order. We show that for each braid b we can efficiently construct a braid [Formula: see text] such that the evaluation of the Jones and HOMFLY polynomials of their closures at a fixed root of unity leads to the same value and that the closures of [Formula: see text] are alternating links.

Let T ( 2 k ) be the set of all tricyclic graphs on 2 k ( k ⩾ 2 ) vertices with perfect matchings. In this paper, we discuss some properties of the connected graphs with perfect matchings, and then determine graphs with the largest index in T ( 2 k ) .

We introduce the concept of a relative Tutte polynomial of coloured graphs. We show that this relative Tutte polynomial can be computed in a way similar to the classical spanning tree expansion used by Tutte in his original paper on this subject. We then apply the relative Tutte polynomial to virtual knot theory. More specifically, we show that the Kauffman bracket polynomial (and hence the Jones polynomial) of a virtual knot can be computed from the relative Tutte polynomial of its face (Tait) graph with some suitable variable substitutions. Our method offers an alternative to the ribbon graph approach, using the face graph obtained from the virtual link diagram directly.

This paper initiates a general study of the connection between graph homomorphisms and the Tutte polynomial. This connection can be extended to other polynomial invariants of graphs related to the Tutte polynomial such as the transition, the circuit partition, the boundary, and the coboundary polynomials. As an application, we describe in terms of homomorphism counting some fundamental evaluations of the Tutte polynomial in abelian groups and statistical physics. We conclude the paper by providing a homomorphism view of the uniqueness conjectures formulated by Bollobás, Pebody and Riordan. Ministerio de Educación y Ciencia MTM2005-08441-C02-01 Junta de Andalucía PAI-FQM-0164 Junta de Andalucía P06-FQM-01649

We establish for which weighted graphs H homomorphism functions from multigraphs G to H are specializations of the Tutte polynomial of G, answering a question of Freedman, Lov´asz and Schrijver. We introduce a new property of graphs called “q-state Potts uniqueness” and relate it to chromatic and Tutte uniqueness, and also to “chromatic–flow uniqueness”, recently studied by Duan, Wu and Yu. Ministerio de Educación y Ciencia MTM2005-08441-C02-01

We generalize Brylawski’s formula of the Tutte polynomial of a tensor product of matroids to colored connected graphs, matroids, and disconnected graphs. Unlike the non-colored tensor product where all edges have to be replaced by the same graph, our colored generalization of the tensor product operation allows individual edge replacement. The colored Tutte polynomials we compute exists by the results of Bollobas and Riordan. The proof depends on finding the correct generalization of the two components of the pointed Tutte polynomial, first studied by Brylawski and Oxley, and on careful enumeration of the connected components in a tensor product. Our results make the calculation of certain invariants of many composite networks easier, provided that the invariants are obtained from the colored Tutte polynomials via substitution and the composite networks are represented as tensor products of colored graphs. In particular, our method can be used to calculate (with relative ease) the expected number of connected components after an accident hits a composite network in which some major links are identical subnetworks in themselves.

The coloured Tutte polynomial by Bollobas and Riordan is, as a generalization of the Tutte polynomial, the most general graph polynomial for coloured graphs that satisfies certain contraction-deletion identities. Jaeger, Vertigan, and Welsh showed that the classical Tutte polynomial is #P-hard to evaluate almost everywhere by establishing reductions along curves and lines. We establish a similar result for the coloured Tutte polynomial on integral domains. To capture the algebraic flavour and the uniformity inherent in this type of result, we introduce a new kind of reductions, uniform algebraic reductions, that are well-suited to investigate the evaluation complexity of graph polynomials. Our main result identifies a small, algebraic set of exceptional points and says that the evaluation problem of the coloured Tutte is equivalent for all non-exceptional points, under polynomial-time uniform algebraic reductions. On the way we obtain a self-contained proof for the difficult evaluations of the classical Tutte polynomial.

A graph G is called T-unique if any other graph having the same Tutte polynomial as G is isomorphic to G. Recently, there has been much interest in determining T-unique graphs and matroids. For example, de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomials, Graphs Combin. 20 (2004) 105–119; A. de Mier, M. Noy, Tutte uniqueness of line graphs, Discrete Math. 301 (2005) 57–65] showed that wheels, ladders, Möbius ladders, square of cycles, hypercubes, and certain class of line graphs are all T-unique. In this paper, we prove that the twisted wheels are also T-unique.

International audience; We prove that every n-vertex cubic bridgeless graph has at least n/2 perfect matchings and give a list of all 17 such graphs that have less than n/2+2 perfect matchings.

This paper introduces a special issue on the Tutte polynomial derived from the Sec- ond Workshop on Tutte Polynomials and Applications, 2005, held at the Centre de Recerca Matem atica, Bellaterra, Catalonia. We discuss the prehistory of Tutte polynomials and two cur- rent areas of research, to what extent a graph is determined by its chromatic or Tutte polynomial and generic versions of Tutte polynomials.

Using matroid duality and the critical problem, we show that certain evaluations of the Tutte polynomial of a matroid represented as a matrix over a finite field GF(q) can be interpreted as weighted sums over pairs f , g of functions defined from the ground set to GF(q) whose difference f – g is the restriction of a linear functional on the column space of the matrix. Similar interpretations are given for the characteristic polynomial evaluated at q. These interpretations extend and elaborate interpretations for Tutte and chromatic polynomials of graphs due to Goodall and Matiyasevich.

It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic polynomials and Tutte polynomials, respectively. Oxley asked which classes of graphs or matroids are determined by their chromatic and flow polynomials together. In this paper, we found several classes of graphs with this property. We first study which graphic parameters are determined by the flow polynomials. Then we study flow-unique graphs. Finally, we show that several classes of graphs, ladders, Möbius ladders and squares of n-cycle are determined by their chromatic polynomials and flow polynomials together. A direct consequence of our theorem is a result of de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomial, Graphs Comb. 20 (2004) 105–119] that these classes of graphs are Tutte polynomial unique.

The structural theory of matchings is used to establish lower bounds on the number of perfect matchings in n-extendable graphs. It is shown that any such graph on p vertices and q edges contains at least (n + 1)!/4[q − p − (n − 1)(2 Delta − 3) + 4] different perfect matchings, where Delta is the maximum degree of a vertex in G.

Identities obtained by elementary finite Fourier analysis are used to derive a variety of evaluations of the Tutte polynomial of a graph G at certain points (a,b) where (a-1)(b-1)@?{2,4}. These evaluations are expressed in terms of eulerian subgraphs of G and the size of subgraphs modulo 2,3,4 or 6. In particular, a graph is found to have a nowhere-zero 4-flow if and only if there is a correlation between the event that three subgraphs A,B,C chosen uniformly at random have pairwise eulerian symmetric differences and the event that @?|A|+|B|+|C|[email protected]? is even. Some further evaluations of the Tutte polynomial at points (a,b) where (a-1)(b-1)=3 are also given that illustrate the unifying power of the methods used. The connection between results of Matiyasevich, Alon and Tarsi and Onn is highlighted by indicating how they may all be derived by the techniques adopted in this paper.

We show that the number of chains of given length in a graph G can be easily found from the Tutte polynomial of G. Hence two Tutte-equivalent graphs will have the same distribution of chain lengths. We give two applications of this latter statement.We also give the dual results for the numbers of multiple edges with given muliplicities.

A classical theorem by Tutte ensures the existence of a Hamilton cycle in every finite $4$-connected planar graph. Extensions of this result to infinite graphs require a suitable concept of an infinite cycle. Such a concept was provided by Diestel and Kuhn, who defined circles to be homeomorphic images of the unit circle in the Freudenthal compactification of the (locally finite) graph. With this definition we prove a partial extension of Tutte's result to locally finite graphs.

We reprove the strong Hanani-Tutte theorem on the projective plane. In contrast to the previous proof by Pelsmajer, Schaefer and Stasi, our method is constructive and does not rely on the characterization of forbidden minors, which gives hope to extend it to other surfaces. Moreover, our approach can be used to provide an efficient algorithm turning a Hanani-Tutte drawing on the projective plane into an embedding., This is the full version of the paper. Its extended abstract appeared in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)

A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph G in terms of what is usually called the deficiency. A subset X of V(G) for which this deficiency is attained is called a Tutte set of G. While much is known about maximum matchings, less is known about the structure of Tutte sets. We explored the structural aspects of Tutte sets in another paper. Here, we consider the algorithmic complexity of finding Tutte sets in a graph. We first give two polynomial algorithms for finding a maximal Tutte set. We then consider the complexity of finding a maximum Tutte set, and show it is NP-hard for general graphs, as well as for several interesting restricted classes such as planar graphs. By contrast, we show we can find maximum Tutte sets in polynomial time for graphs of level 0 or 1, elementary graphs, and 1-tough graphs.

We define and study the Tutte polynomial of a hyperplane arrangement. We introduce a method for computing the Tutte polynomial by solving a related enumerative problem. As a consequence, we obtain new formulas for the generating functions enumerating alternating trees, labelled trees, semiorders and Dyck paths.