graph theory
Can anyone give me an example of a graph with vertex connectivity = $1$, edge connectivity = $3$, and minimum degree = $4$?
Also, I'm looking for a $2$-connected graph with a $uv-$path from which no other $uv-$path is internally disjoint (both edge and vertex disjoint)?
Thanks!
Let $G$ be a graph and let $\kappa(G)$ be the size of any minimum vertex separating set of $G$, $\lambda(G)$ be the minimum size of any edge separating set of $G$, and let $\delta(G)$ be the minimum degree of $G$. It is well known that $$\kappa(G)\le\lambda(G)\le\delta(G).$$ Since $\delta(G)=2$ and $G$ is connected then $\kappa(G)=1\text{ or }2$. Can you show that $\kappa(G)\ne 1$?
When you are drawing graphs, edges should never meet unless they are crossing or share a vertex in common and they should only meet in those locations. The way you have drawn your graph seems to indicate that $\deg(v_5)=3$ when it is really true that $\deg(v_5)=4$. Similarly for $v_7$.
Would separating $A$ into two nodes connected by one edge work? Also, the minimum degree of your graph is $2$ at each of the four corner nodes.
The graph with the largest minimum degree, lowest edge connectivity, and lowest vertex connectivity is formed by connecting two complete graphs with one singular edge like a bridge.
Best Answer
For the first one, take two $K_5$ (complete graph with 5 vertices), add one node in the middle, which you connect to three vertices of one of the $K_5$ and three of the other $K_5$.
Edge connectivity is $3$ and removing the middle node disconnects the graph.
For the second one, take a hamiltonian circle.