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 …
Math and Comp Sci: Graph theory: Max trail length on complete graph, Kn Read more »
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 …
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 …
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 …
Math & Comp Sci: Graph theory: what is an elementary subdivision? Read more »
The tutor defines cut set with a couple of examples. When one imagines a cut set, one imagines removing edges from a graph, but not the vertices they connect. In this context, we are thinking of undirected graphs. A cut …
Math & Comp Sci: Graph theory: what is a cut set? Read more »
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 …