TITLE: How can ($A$ and $B$ $\implies$ $C$) and ($C$ and $B$ $\implies$ not $A$) together imply (not $A\iff B$)?
QUESTION [3 upvotes]: I encountered this two statements when I tried to understand the proof of Kuratowski Theorem.

Any minimal nonplanar graph and it has no Kuratowski subgraphs, then it must be at least 3 connected.
An at least 3 connected graph and it has no Kuratowski subgraphs, then it must be planar.

My question is how can these two statements imply the Kuratowski Theorem?
If we let:
$A=$ minimal nonplanar graph,
$B=$ no Kuratowski subgraphs,
$C=$ at least 3 connected,
Then how can we understand:
$A\wedge B\implies C$
$C\wedge B\implies A'$, where $A'$ is not $A$.
implies
$A'\iff B$
I am not asking about the details about the proof, but only the logic behind how can those two statements imply the third (from the language of logic).
Thanks.

REPLY [0 votes]: Kuratowski's Theorem is an example of TONCAS (The Obvious Necessary Condition is Also Sufficient). That is, the "obvious" necessary condition for a graph to be planar is that it has no Kuratowski subgraph. This is because planarity is a hereditary property (all subgraphs of a planar graph are still planar, so planar graphs can't have nonplanar subgraphs such as $K_{3,3}$ or $K_5$). Hence, it is easy to see that:
$$
\neg A \implies B
$$
The surprising part of Kuratowski's Theorem is the converse, which is what the proof is all about:
$$
B \overset{?}{\implies} \neg A
$$
To this end, suppose that $B$ holds true. We want to show that $\neg A$ holds true. Suppose, towards a contradiction, that $A$ holds true. Then since $A \land B \implies C$, we know that $C$ holds true. But then since $C \land B \implies \neg A$, we know that $\neg A$ holds true, a contradiction. Thus, we conclude that $\neg A$ holds true, as desired.
{"set_name": "stack_exchange", "score": 3, "question_id": 1814238}