1
$\begingroup$

I've been stuck on this for a while. First, some definitions, in case my prof uses different terms than everyone else.

Minimum degree: This is equal to the number of edges connected to the vertex that has the least number of edges incident to it.

Connectivity: The larges number k, such that the graph is k-connected.

k-connected: A graph G is k-connected if there doesn't exist any set of vertices, call it X, such that the size of X is less than k, and G - X is disconnected.

Edge Connectivity: The larges value l, such that that there doesn't exist a set of edges, call it F, such that the size of F is less than l, and G - F is disconnected

So the question asks us to find a graph that has a high minimum degree but low connectivity and edge connectivity. I think I've made one with high minimum degree and low connectivity enter image description here

The above is 1-connected but has minimum degree of 4.

However, I can't figure out a graph that has high minimum degree but low edge connectivity. Would appreciate some help.

Thanks.

I made this graph on https://illuminations.nctm.org/Activity.aspx?id=3550 EDIT: I made a mistake. The four corner vertices had degrees of 2. This following graph is the graph I was looking for: enter image description here

It has a minimum degree of four. A connectivity of 1 and edge connectivity of 1. Thanks for the help!

$\endgroup$
2
$\begingroup$

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.

Actual Example Graph

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.

$\endgroup$
  • $\begingroup$ Yes. I can't beleive I didn't think of that. I need to take a break... Thank you very much. $\endgroup$ – The_Questioner Oct 3 '16 at 1:27
  • $\begingroup$ Actually, the edit you made gives a connectivity of 3. $\endgroup$ – The_Questioner Oct 3 '16 at 1:31
  • $\begingroup$ My bad. All I need to do is remove the top and bottom edges and put them somewhere else. $\endgroup$ – AlgorithmsX Oct 3 '16 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.