# Find simple graphs of diameter 3 where edge connectivity doesn't equal minimum degree

I've seen a question here which is about

Prove that in a simple graph of diameter 2 the edge connectivity is equal to the minimum degree

But I would like to show that this is the best bound by finding an infinite class of connected graphs of diameter 3 where the minimum degree doesn't equal the edge connectivity.

Consider the graphs obtained by joining two complete graphs on at least three vertices by a bridge; the number of vertices on each side need not be equal. The simplest case, with two copies of $K_3$, is

*     *
|\   /|
| *-* |
|/   \|
*     *


(MathWorld calls such graphs, with equal vertex counts on each side, barbell graphs). All such graphs, by virtue of the bridge, are only 1-edge-connected; they are also easily seen to have diameter 3 and minimum degree at least 2. Therefore, this is an infinite set of diameter-3 graphs where edge connectivity and minimum degree are unequal.

A simple counter Example is the path 4 graph denoted $P_4$ which is just this :

$* -- * -- * -- *$ so the graph diameter is $3$ and edge connectivity is $1$ since removing any edge will result to disconnect the graph but also the first and last vertex has degree $1$.

• So minimum degree = edge connectivity in your example - I improved the question title to show that what is desired is a graph where that is not true. – Joffan Mar 15 '17 at 15:25
• And now, this does not answer the question. – Parcly Taxel Mar 15 '17 at 15:55
• @ParclyTaxel It never answered the text of the question. – Joffan Mar 15 '17 at 16:06