The most memorable comment from Daniel Bienstock’s first optimization lecture was “we use induction when there is a structure”. But upon my question “how about contradiction” instead of answering, he advised to read a lot of proof.

Currently contradiction reminds me of “Jekyll and Hyde”; one half killed by the contradicted other half. This object can be a tree, minimum weight spanning tree, set of vertices reachable from S_z, set of add-able edges to the first matroid. These involve at least two prescriptions of opposite direction acting as the source of uniquely defining the object in the first place. All in all, there Jekyll and Hyde are destined to identify themselves as a whole. This is what I call “uniqueness” below. What Dan mentioned as “cruelty” is the remaining next stage to explain.

I am starting this writing to document two subcategories of uniqueness — what I judged to be the core of contradiction proof.

2.1. Feasibility uniqueness.

– To prove unique path between vertices in tree, we argue: Given forest matroid, assuming the tree has two path between vertices, “feasibility uniqueness” in tree contradicts with two cycles.

2.2. Optimality uniqueness.

– To prove uniqueness in optimality, we argue: Given convexity of problem, assuming we can find augmenting path in optimal state, “optimality uniqueness” contradicts with the existence of augmenting path.

– Minimum weight spanning tree doesn’t have crossings is proved by assuming crossing then attacking optimality of “min weight”. Commander of this attack is objects’ another trait “spanning tree” which implies the existence of path. With this digged up destructor (other example is edge leaving R from Korte Vygen p.346.to construct improved certificate.

– R whose definition is set of vertices reachable from S_x is Jikyl and Hide.