0
$\begingroup$

(1) If degree of every node in an $n$-vertex graph is at least $n/2$ then is the graph always connected?

Can we reduce $n/2$?

(2) Suppose distance between a particular two nodes is $>n/2$ does that mean there is a node which when removed disconnects the graph? How to find this node?

Can we reduce $n/2$ here?

$\endgroup$
  • $\begingroup$ For the second question, an idea : any two paths from $u$ to $v$ (the particular nodes) have length $>n/2$, so they must intersect at some point (the case where there's only one path being obvious) $\endgroup$ – Max Jan 27 '17 at 22:02
0
$\begingroup$

OUTLINE

Suppose graph is disconnected, then there are at least 2 components, and in the one that has the smaller number of vertices, the degree cannot exceed $n/2$, which is a contradiction to your min degree.

Can you construct a graph that demonstrates this bound is sharp?

$\endgroup$
0
$\begingroup$

For a constructive proof on (1):

First consider a node $v$ that has degree $ \ge n/2$. Then call $W$ the set of nodes that are not directly connected to $v$ noting that $|W|\le n-n/2-1 = n/2-1$. Then consider any node $w \in W$ and note that it must be connected to some node outside $W$, i.e some node that is connected to $v$. Thus the graph is connected.

We can reduce the minimum degree value here to $\ge \lfloor n/2\rfloor$, but smaller values allow the separation of the graph into two complete graphs each with half the nodes.

For question (2) a path length of $>n/2$ between chosen nodes $u$ and $v$ indicates that there is a node on that path that can be removed to break the path and hence disconnect the graph, but I can't quite put the argument together with the rigor I would like.

Certainly though the limit cannot be much reduced as the cycle graph with even nodes has $2$ paths of length $n/2$ between any two points, so there is no single node can be removed to disconnect the graph.

$\endgroup$

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.