## Math and Comp Sci: Graph theory: Max trail length on complete graph, Kn

The tutor considers a problem from Grimaldi about max trail length on Kn. For a briefing about the complete graph Kn, check my post from yesterday. In graph theory, a trail is a route that doesn’t repeat any edges. Unlike …

Tagged with: , , ,

## Math & Comp Sci: Graph theory: Complete graph

The tutor introduces the idea of the complete graph. The complete graph on n vertices, Kn, means the graph in which each vertex is connected to each other one. When two vertices are connected by an edge, they can be …

## Math & Comp Sci: Graph theory: Hamilton cycle

The tutor proves the existence of a Hamilton cycle under certain conditions. A Hamilton cycle, named for the Irish mathematician Sir William Rowan Hamilton, is a path that visits each vertex of a graph exactly once before returning to the …

## Math & Comp Sci: Graph theory: what is an elementary subdivision?

The tutor shows the easy concept, from graph theory, of elementary subdivision. An elementary subdivision on a graph replaces one edge by two, with a new vertex installed between them. Consider the following two graphs: Graph 1 Graph 2 Graph …

Tagged with: ,

## Math: graph theory: a textbook example

The tutor offers a solution to a textbook graph theory question. On page 556 (Grimaldi) is the following question: Let G be a loop-free connected undirected 3-regular graph (every vertex has degree 3), such that |E| = 2|V| – 6 …