Find a graph such that $\kappa(G) < \lambda(G) < \delta(G)$

How would I go about constructing a graph that satisfies this inequality? I am new to graph theory so I'm not sure where to start. Note that:

$$\kappa(G)$$ is the vertex-connectivity of G, the size of the smallest separating set of G. (A separating set is a set of vertices of G whose deletion from the graph makes the graph become disconnected).

$$\lambda(G)$$ is the edge-connectivity of G, the size of the smallest disconnect set of G. (A disconnected set is a set of edges of G whose deletion from the graph makes the graph become disconnected).

$$\delta(G)$$ is the minimum degree of G (i.e. the degree of the vertex of G with the minimum degree).

• Could you please define $\kappa(G),\lambda(G)$ and $\delta(G)$ for us non-graph theorists around here? :) Commented Oct 11, 2019 at 1:32
• @LuizCordeiro Updated.
– A.B
Commented Oct 11, 2019 at 2:15
• What is $\delta(G)$? For the first inequality, consider two large, disjoint cliques, and add a new node with an edge to every node in the two cliques. Then removing that new node disconnects the graph, but you'd need to remove many edges to disconnect the graph.
– J.G
Commented Oct 11, 2019 at 2:40

Let $$G$$ be the following graph:

Then $$\kappa(G)=1$$ (remove its middle point), $$\lambda(G)=2$$ (remove $$a$$ and $$b$$) and $$\delta(G)=3$$.

• Perfect, thank you so much! If I may ask, how do you think about this when you are trying to come up with a graph?
– A.B
Commented Oct 11, 2019 at 3:06
• Well, $\kappa(G)$ should be small, so I'll just take two separated graphs (like the squares which form $G$ in the answer) joined by a single point. Removing that point will disconnect the graph. Now $\lambda(G)$ should also be small-ish. Since removing the middle point makes the graph disconnected, removing the edges around it will also do so. We just need to ensure there are at least two edges "in each direction" to make $\lambda(G)>\kappa(G)$. Two squares do fine (two triangles would also work). I then added the middle points in the squares to make $\delta(G)$ larger. Commented Oct 11, 2019 at 3:14
• @K.B. So in some way, we just start with one of the desired properties ($\kappa$ small), and then modify the result step-by-step to have the extra properties ($\lambda$ larger than $\kappa$, but not too much, then $\delta$ large). Commented Oct 11, 2019 at 3:15

Given integers $$k,\ell,d$$ with $$1\le k\le\ell\le d$$, here's how you can construct a graph $$G$$ with $$\kappa(G)=k$$, $$\lambda(G)=\ell$$, and $$\delta(G)=d$$.

Take five disjoint sets $$V_1,V_2,V_3,V_4,V_5$$ with $$|V_1|=1$$, $$|V_2|=d$$, $$|V_3|=\ell$$, $$|V_4|=k$$, $$|V_5|=d$$, and take a surjection $$f:V_3\to V_4$$.

The vertex set of $$G$$ is $$V_1\cup V_2\cup V_3\cup V_4\cup V_5$$.

For the edge set of $$G$$ take all edges $$xy$$ where $$\{x,y\}\subseteq V_1\cup V_2$$ or $$\{x,y\}\subseteq V_2\cup V_3$$ or $$\{x,y\}\subseteq V_4\cup V_5$$, and all edges $$xy$$ where $$x\in V_3$$ and $$y=f(x)\in V_4$$.

Note that $$G$$ can be disconnected by removing either the $$k$$ vertices in $$V_4$$ or the $$\ell$$ edges between $$V_3$$ and $$V_4$$, and that the vertex in $$V_1$$ has degree $$d$$. A little consideration will show that in fact $$\kappa(G)=k$$, $$\lambda(G)=\ell$$, and $$\delta(G)=d$$.

• +1 Ah, that makes sense now. Your notation is fine, I just read it wrong. Commented Dec 1, 2020 at 6:22

$$\kappa(G)$$ is the vertex-connectivity of G.

$$\kappa'(G)$$ is the edge-connectivity of G.

$$\delta(G)$$ is the minimum degree of G.

Reference

ɑ(G) is the vertex connectivity of G.

λ(G) is the edge connectivity of G.

δ(G) is the minimum degree of G.

• They needed a graph with $κ(G) < λ(G) < δ(G)$ but you gave a graph with $κ(G) = λ(G) < δ(G)$ Commented Jun 10 at 20:17

watch out! mma GraphData hasn't implemented all graphs for vertex-number =8,9,10,11,12...

You can use Mathematica GraphData function to find the answer.

Here is an example.

func = {#, GraphData[#, "VertexConnectivity"],
GraphData[#, "EdgeConnectivity"],
GraphData[#, "MinimumVertexDegree"]} &;
selectedGraphs =
GraphData[All] // Map[func, #] & //
Select[#, (Part[#, 2] < Part[#, 3] && Part[#, 3] < Part[#, 4]) &] &
{{{"Quartic", {11, 1}}, 1, 2, 4}}   (* just find this, maybe exsits more*)

(*Note that mma GraphData hasn't implemented all graphs for vertex-number =8,9,10,11,12...*)
(*Plot the satisfied graphs*)
GraphicsGrid[
Partition[GraphData /@ Map[Part[#, 1] &, selectedGraphs], UpTo[5]]]

For this graph,

• vertex-connectivity is $$1$$
• edge-connectivity is $$2$$
• minimum-vertex-degree is $$4$$