so im spontaniously asked to do a problem for 173 number three on homework 7.
its a structural induction to show an induction hypothesis is true for every nondirectional graph.
so i come up with a grammar to describe all graphs
a single vertex is a graph.
A not connected to B is a graph where A and B are graphs
A connected by a new edge to B is a graph if A and B are graphs.
this doesn't produce the set of all nondirectional graphs and i realized this when a student asked me to produce the "triangle" graph and i realized i couldn't.
the correct production is
a single vertex is a graph
A not connected to B is a graph iff A and B are graphs
C with an extra edge is a graph iff C was a graph and not saturated with edges.
so much easier.
