Suppose we have a conjecture on graph theory that can be (dis)proved by means of

Question

Suppose we have a conjecture on graph theory that can be (dis)proved by means of a counter example, then, is it true that every alternative (dis)proof of the conjecture can be mapped to a counter example?

This is in the general case, but for instance, can any proof that the hadwiger's conjecture is false be mapped to a counter example, i.e., a particular graph?

Or,

Can any proof about a purported property P(L) of a language L, susceptible of being (dis)proved by a counter example, be mapped to a particular word, say w meaning w a counter example, i.e., P(L):=FALSE since w exists?

Explanation / Answer

Your question isn't entirely clear, but it seems you're asking if every false graph property has a counterexample. Obviously this is true: by definition there must be some graph for which the property doesn't hold. On the other hand, a proof that the property doesn't hold for all graphs may not necessarily give an example of such a graph; this is called a non-constructive proof.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.