Planarity and duality of finite and infinite graphs

We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.     

Duality of infinite graphs

Some basic results on duality of infinite graphs are established and it is proven that a block has a dual graph if and only if it is planar and any two vertices are separated by a finite edge cut. Also, the graphs having predual graphs are characterized completely and it is shown that if $\text{G}{}^1$ is a dual and predual graph of G, then G and $\text{G}{}^1$ can be represented as geometric dual graphs. The uniqueness of dual graphs is investigated, in particular, Whitney's 2-isomorphism theorem is extended to infinite graphs. Finally, infinite minimal cuts in dual graphs are studied and the characterization (in terms of planarity and separation properties) of the graphs having dual graphs satisfying conditions on the infinite cuts, as well, is included.     

Wagner's theorem for Torus graphs

Wagner's theorem (any two maximal plane graphs having p vertices are equivalent under diagonal transformations) is extended to maximal torus graphs, graphs embedded in the torus with a maximal set of edges present. Thus any maximal torus graph having p vertices may be diagonally transformed into any other maximal torus graph having p vertices. As with Wagner's theorem, a normal form representing an intermediate stage in the above transformation is displayed. This result, along with Wagner's theorem, may make possible constructive characterizations of planar and toroidal graphs, through a wholly combinatorial definition of diagonal transformation.     

A classification of 4-connected graphs

Having observed Tutte's classification of 3-connected graphs as those attainable from wheels by line addition and point splitting and Hedetniemi's classification of 2-connected graphs as those obtainable from K₂ by line addition, subdivision and point addition, one hopes to find operations which classify n-connected graphs as those obtainable from, for example, K_n+1. In this paper I give several generalizations of the above operations and use Halin's theorem to obtain two variations of Tutte's theorem as well as a classification of 4-connected graphs.     

An improved version of Lloyd's theorem

The generalisation of Lloyd's theorem to distance-transitive graphs can be improved in the case of antipodal graphs by looking at the derived graph. In the case of binary perfect codes the roots of the Lloyd polynomial are even integers. This can be applied to give a short proof of the binary perfect code theorem.     

Milnor's μ-invariants,Massey products and Whitney's trick in 4 dimensions

We present the failure of Whitney's lemma in dimension 4 from the homotopical and topological viewpoints. Those are detected by Massey products. The invariants for the examples represented by framed links are computed in terms of Milnor's $\text{μ}$-invariants.     

Deformations and transversality of pseudo-holomorphic discs

We prove analogs of Thom’s transversality theorem and Whitney’s theorem on immersions for pseudo-holomorphic discs. We also prove that pseudoholomorphic discs form a Banach manifold.     

Hamiltonian paths in oriented graphs

A short proof is given of Meyniel's theorem on Hamiltonian cycles in oriented graphs. Analogous conditions are obtained for a graph to be Hamiltonianconnected.     

On the Number of Precolouring Extensions

We investigate the number of proper λ -colourings of a hypergraph extending a given proper precolouring. We prove that this number agrees with a polynomial in λ for any sufficiently largeλ , and we establish a generalization of Whitney’s broken circuit theorem by applying a recent improvement of the inclusion–exclusion principle.     

A generalization of Tutte's 1-factor theorem to countable graphs

A criterion is proved for a countable graph to possess a perfect matching, in terms of “marriage” in bipartite graphs associated with the graph. In the finite case, this yields Tutte's 1-factor theorem. The criterion is conjectured to be valid for general graphs.     

On matroid connectivity

Three types of matroid connectivity, including Tutte's, are defined and shown to generalize corresponding notions of graph connectivity. A theorem of Tutte on cyclically 3-connected graphs, is generalized to matroids.     

Tabloïdes

A tabloïde is composed of two finite sets, E (the set of the rows) and F (the set of the columns), and of a function f: $\text{P}$(E) × $\text{P}$(F) → $\text{N}$, which is a Whitney's rank in its two variables. There are tabloids associated to matrices, to bipartite graphs and to ordinary graphs respectively in relation to linear rank, matchings and gammoids. Some of the properties of matrices can be generalized to tabloids (transposition, direct sum, inverse, product…). The properties of bipartite graphs which consists in “transmission” of matroids by matchings is used to define a class of tabloids (which strictly contains those which are associated to matrices). Finally, the problem of the representation of a tabloid on a field is studied.     

A refined Hurwitz theorem for imbeddings of irredundant Cayley graphs

Hurwitz's theorem states that the order of any finite group acting on a surface of genus γ > 1 is bounded by 168(γ ? 1). It can be refined to give useful information about groups whose order is near this bound. In this paper, similar results are obtained for Cayley graphs imbedded in a surface of genus γ. These results have important implications for the classification of Cayley graphs of low genus and the number of Cayley graphs of a given genus.     

Algebraic characterizations of outerplanar and planar graphs

A drawing of a graph in the plane is even if nonadjacent edges have an even number of intersections. Hanani’s theorem characterizes planar graphs as those graphs that have an even drawing. In this paper we present an algebraic characterization of graphs that have an even drawing. Together with Hanani’s theorem this yields an algebraic characterization of planar graphs. We will also present algebraic characterizations of subgraphs of paths, and of outerplanar graphs.     

Note on Halin's theorem on minimally connected graphs

In this note it is shown that any finite directed graph of strong connectivity n contains either a vertex with indegree n, a vertex with outdegree n, or an edge whose removal does not decrease the connectivity. This is a directed graph counterpart of Halin's theorem on undirected graphs. It is pointed out that only a few preparations and modifications are necessary to make his proof valid for directed graphs.     

Helly-type theorems for pseudoline arrangements in P2

We prove duals of Radon's theorem, Helly's theorem, Carathéodory's theorem, and Kirchberger's theorem for arrangements of pseudolines in the real projective plane, which generalize the original versions of those theorems for plane configurations of points. We also prove a topological generalization of the pseudoline-dual of Helly's theorem.     

Hurwitz' theorem implies Rouché's theorem

It is well known that Hurwitz's theorem is easily proved from Rouché's theorem. We show that conversely, Rouché's theorem is readily proved from Hurwitz' theorem. Since Hurwitz' theorem is easily proved from the formula giving the number of roots of an analytic function, our result thus gives also a simple proof of Rouché's theorem.     

Colorful subgraphs in Kneser-like graphs

Combining Ky Fan’s theorem with ideas of Greene and Matoušek we prove a generalization of Dol’nikov’s theorem. Using another variant of the Borsuk–Ulam theorem due to Tucker and Bacon, we also prove the presence of all possible completely multicolored t-vertex complete bipartite graphs in t-colored t-chromatic Kneser graphs and in several of their relatives. In particular, this implies a generalization of a recent result of G. Spencer and F.E. Su.     

Connectedness and classification of certain graphs

G. A. Dirac gives a necessary arc family condition for a graph to be n-vertex connected. The converse of this theorem of Dirac is false. Mesner and Watkins obtained partial results for additional conditions that the converse be true. A graph G which satisfies Dirac's arc family condition is now completely classified in terms of the order of V(G), the structure of parts of minimum cutsets of G and consequent lower bounds for vertex-connectivity of G. Examples show that all lower bounds are best possible. Several distinct extensions of Whitney's necessary and sufficient condition for a graph to be n-vertex connected also appear as corollaries. Finally, examples are presented to show a graph which satisfies a given n-family arc condition. However, the same graph does not satisfy a very similar (n ? 1)-family arc condition where exactly one arc has been eliminated from the statement of the original n-family arc conditon.     

Perfect codes in graphs

The classical problem of the existence of perfect codes is set in a vector space. In this paper it is shown that the natural setting for the problem is the class of distance-transitive graphs. A general theory is developed that leads to a simple criterion for the existence of a perfect code in a distance-transitive graph, and it is shown that this criterion implies Lloyd's theorem in the classical case.