Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.


quasi
Posts:
11,721
Registered:
7/15/05


Re: Note to Quasi from Bill
Posted:
Jun 21, 2013 5:39 AM


Some context restored ...
>quasi: >What are MA vertices? > >bill: >mutually adjacent vertices. >So take 4 MA vertices. >Then connect vertex 5 to each of the first four.
That would make a K5 which fails to satisfy your stated hypothesis. And if you keep 5 vertices but drop an edge, then ... >quasi: >Any noncomplete graph with 5 vertices is 4colorable.
Thus, it would also satisfy your conclusion. So it wouldn't be a counterexample. A counterexample must satisfy the hypothesis but fail the conclusion.
>bill: >Not if the graph is nonplanar.
Your conjecture never specified anything about planarity. Perhaps you want to revise your conjecture? If so, please state it fully and precisely.
Every noncomplete graph with exactly 5 vertices is planar.
>bill: >If there are no forceable sets of four vertices the graph >must be 4 colorable.
What are you claiming. Can you state it precisely?
What are forcible sets of 4 vertices? Do you mean subgraphs isomorphic to K4?
Are you restricting to planar graphs?
If so, then of course your graph will be 4 colorable (by the 4 Color Theorem).
If you are not restricting to planar graphs, then your claim is almost certainly false.
But in any case, your claim needs to be made more precise.
>quasi: >(as relates to your original claim): >Except that I've already shown you a counterexample.
>Is your example planar?
Of course not.
The graph I posted yields a _counterexample_ to your original conjecture.
Which means:
(1) It satisfies your stated hypothesis, that is, it has no subgraph isomorphic to K5
but
(2) It fails your stated conclusion, that is, it's not 4colorable (and hence is also nonplanar).
quasi



