Prove that if $G$ is a graph with $2k+1$ nodes and the degree of each vertex is $k$, then $G$ is a connected graph

Question

I'm trying to prove that if $G$ is a graph with $2k+1$ nodes ($k \in \mathbb{Z}$) and the degree of each vertex is $k$, then $G$ is a connected graph, and what's the size of its diameter? does someone knows how to write a proof? thanks.

Answer 1

This is probably not a standard proof as I don't know much graph theory but here is one solution. Denote one vertex as $\alpha$ and denote the $k$ vertices that $\alpha$ is connected to as $A.$ Denote the set containing the remaining $k$ vertices as $B.$ Note that the subgraph consisting of $A$ and $\alpha$ is connected. Now consider any vertex in $B.$ Every vertex in $B$, call it $\beta$, must have an edge that connects it to a vertex in $A \cup \{\alpha\}$ as the maximum number of edges that connects $\beta$ to a vertex not in $A \cup \{\alpha\}$, i.e. a vertex in $B$ is $k - 1.$ Thus, every vertex in $B$ is connected to a vertex in $A \cup \{\alpha\}$, hence the graph is connected.

The diameter should be 2. The upper bound is clearly 3. But to show that it cannot be 3, let $\alpha$ be a vertex with eccentricity 3. Consider a path $\alpha \rightarrow \alpha' \rightarrow \alpha'' \rightarrow \alpha'''$ (and there is no shorter path from $\alpha$ to $\alpha'''$). Let $C$ be a set of $k - 1$ vertices that $\alpha$ is connected to. That is $\alpha$ is connected to just $\alpha'$ and the points in $C.$ Let $D$ be the set of the remaining $k - 2$ vertices. Note that $\alpha'''$ cannot be connected to any point in $C$ as well as $\alpha'$ and $\alpha.$ Thus, the only other vertices that $\alpha'''$ can be connected to are points in $D.$ But $D$ is of size $k - 2$ so this is a contradiction. So 2 should be the diameter.

Answer 2

Suppose G is not connected, hence it contains at least two disjoint components. Any vertex in one of those subgraphs is degree k, so its component has at least 1+k vertices. Same applies to the other component(s), so G would have at least 2k+2 vertices, contrary to the assumption.

Which implies the additional supposition on disconnectiveness is false.