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.