thomas mattman

My students have come up with the following conjecture. I'm out of my
depth and would appreciate any suggestions or references.

Conjecture: If a (simple, connected) graph is such that every adjacent
pair of vertices has at least 3 common neighbours, then the graph is
4-connected.

More generally, if a graph is such that every adjacent pair of
vertices has at least m common neighbours, then the graph is
m+1-connected.

True and well known? Counterexamples? Maybe true, but difficult to
prove?

Thanks!

Thomas

luis goddyn

Counterexample:
Join two copies of the complete graph on m+2 vertices, by identifying
one vertex from each of them. The resulting graph satisfies the
hypothesis and is not 2-connected.
Luis Goddyn

thomas mattman

Thanks to Luis as well as Dave Wagner and Mingquan Zhan who replied
privately. Dave Wagner also pointed out that the result is true if one
is looking for m+1-EDGE-connectivity.

The students came up with that question as part of their attempt to
prove the following conjecture.

Conjecture: Let G be a simple, connected graph such that each pair of
adjacent vertices has at least m neighbours in common. Then G has a
K_{m+2} minor.

They've proved the case when m=2 and believe they have an argument
when m=3. However their approach bogs down for bigger m.

Again, I'd appreciate any help with this one.

Thanks!

Thomas
TMattman@CSUChico.edu