Do 3n-5 Edges Force a Subdivision of K5?

Abstract

A conjecture of Dirac states that every simple graph with n vertices and 3n - 5 edges must contain a subdivision of K5. We prove that a topologically minimal counterexample is 5-connected, and that no minor-minimal counterexample contains K sub 4 - e. Consequently, we prove Dirac's conjecture for all graphs that can be imbedded in a surface with Euler characteristic at least -2.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1990
Accession Number
ADA221469

Entities

People

  • Andre E. Kezdy
  • Patrick J. Mcguinness

Organizations

  • University of Illinois Urbana–Champaign

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Classification
  • Computational Science
  • Computer Science
  • Contracts
  • Equations
  • Graph Theory
  • Guarantees
  • Illinois
  • Mathematics
  • Military Research
  • Security
  • Separators
  • Terminals
  • Triangles
  • Universities

Fields of Study

  • Mathematics

Readers

  • Calculus or Mathematical Analysis
  • Graph Algorithms and Convex Optimization.