Prove that for any graph G, the connectivity is less that the minimum degree

  • Context: Graduate 
  • Thread starter Thread starter sunnyceej
  • Start date Start date
  • Tags Tags
    Degree Graph Minimum
Click For Summary

Discussion Overview

The discussion centers around the relationship between the connectivity of a graph \( G \) and its minimum degree. Participants explore whether the connectivity \( \kappa(G) \) is less than or equal to the minimum degree \( \delta(G) \) for any graph.

Discussion Character

  • Debate/contested

Main Points Raised

  • One participant asserts that \( \kappa(G) \leq \delta(G) \) and seeks a proof for this statement.
  • Another participant requests definitions for the terms used in the discussion, indicating a need for clarity.
  • A different participant proposes a hypothetical scenario where the connectivity is assumed to be greater than the minimum degree and questions how many elements need to be removed to disconnect a vertex with minimum degree from the rest of the graph.
  • One participant reiterates the original claim about the relationship between connectivity and minimum degree while providing a specific example of a simple graph with two vertices and one edge, questioning the implications of the claim in this case.
  • A later reply suggests that the original post's title may need clarification regarding whether the relationship is strictly less than or less than or equal to.

Areas of Agreement / Disagreement

Participants do not appear to reach a consensus, as there are competing views regarding the relationship between connectivity and minimum degree, and the discussion remains unresolved.

Contextual Notes

There are limitations in the definitions and assumptions presented, particularly regarding the terms used and the implications of the example graph provided.

sunnyceej
Messages
15
Reaction score
0
prove that for any graph G, kappa (G) ≤delta (G).
 
Physics news on Phys.org
define your terms.
 
suppose the connectivity is larger than min deg and look at the vertex v with min deg.
How many elements (nodes / edges) need to be removed to disconnect v from the rest of G?
 
sunnyceej said:
prove that for any graph G, kappa (G) ≤delta (G).

What about the graph {(x,y)} on two vertices {x,y}, i.e., a tree with one edge?

EDIT: OP, you may want to square up your title with your question. Do you want less-than, or less-than-or-equal-to?
 

Similar threads

MHB Minimum Degree of a Random Graph (Probabilistic Method)
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Find Smallest Subtree of G w/ Nodes from S
  • · Replies 5 ·
Replies
5
Views
2K
Graduate Is Your Graph Homeomorphic to a Sphere?
  • · Replies 3 ·
Replies
3
Views
2K
Domination number of a graph G
  • · Replies 9 ·
Replies
9
Views
2K
Undergrad Finding if a subgraph of a minimal non-planar graph is maximal planar
  • · Replies 1 ·
Replies
1
Views
2K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
6K
Undergrad Understanding a Graph Theory Proof
  • · Replies 3 ·
Replies
3
Views
1K
Proving uniqueness of almost irregular graphs with equal degrees for n=2k
  • · Replies 3 ·
Replies
3
Views
3K
MHB Bipartite Graphs: Does $\alpha(G) =|U|$?
  • · Replies 1 ·
Replies
1
Views
2K