1

 The purpose of this undergraduate research project in graph theory was
to resolve conjectures generated by Graffiti.pc about graphs that are
traceable.
 Parttime project that began in the spring.

2

 A graph is said to be traceable (or has a Hamiltonian Path) if the all
of the vertices of the graph can be visited exactly once.

3

 The degree of a vertex is the number of edges incident to the vertex.
The minimum of the degrees of the vertices is called the minimum degree
of the graph.

4

 Theorem (Dirac 1952). Let n be the number of vertices of the graph. If
the minimum degree of a graph is greater than or equal to (n1)/2, then
the graph is traceable.

5

 Conjecture. If there are at most
two vertices of degree 1 in a graph G, then the graph is traceable
 Counterexample

6

 Graffiti.pc was also asked to make necessary conditions for traceable
graphs.
 Conjecture. If the graph G is traceable, then the minimum degree of G
is at least half of k, where k is the number of vertices of minimum
degree.

7

 We resolved 29 conjectures of which 2 were true.
 An example of a conjecture that was proven:
 Theorem. If G is a traceable graph, then number of vertices of degree 1
is at most twice the minimum degree.
 Future project direction: Narrow the topic a little bit, by asking the
program, Graffiti.pc to focus on bipartite graphs that are traceable.
