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 …
The tutor attempts to strip the pigeonhole principle to bare wires with a simple problem. I discussed the pigeonhole principle in my May 23/14 and Oct 29/14 posts. The concept is that, with n+1 pigeons going to n pigeonholes, one …
Math: counting: pigeonhole principle, yet another example Read more »
The tutor defines, in the context of symbolic logic, contradiction, with a couple of examples. For those new to symbolic logic, my previous post leads back to others that will fill the gaps. A contradiction is a compound statement that …
The tutor follows up about tautology with another example. For grounding about the symbols, etc, readers may want to refer to my Feb 12 post. In my Feb 13 post I defined tautology with a simple example. Today, I’ll give …
Math & Comp Sci: Symbolic Logic: another tautology Read more »
The tutor continues about logic, defining tautology with an example. In yesterday’s post I began about symbolic logic. A tautology is a compound statement that is always true. For an example, consider the following two statements: p: Today it will …
The tutor lays a foundation for posts about symbolic logic. In logic, shorthand such as p→q is used; it means “p implies q.” p ∨ q means “p or q.” p ∧ q means “p and q”. ¬p means “not p”. p, …