3-connected graph- Proof

Prove that there is no 3-connected graph with 7 edges.

My solutions:

Let G be a simple, connected graph. $\delta \left ( G \right )$ (minimum degree) for k-connected graph is: $\delta(G)\geq k$. So in our case $\delta(G)\geq 3$.

Let $\delta(G)= 3$, then according to definition $\left | V\left ( G \right ) \right |> 3$ ( $\left | V\left ( G \right ) \right |$ number of vertices). Let $\left | V\left ( G \right ) \right |= 4$, then $\left | E\left ( G \right ) \right |=6$.

Does it prove the statement?

1 Answer

Suppose that $G$ is a $3$-connected graph with $7$ edges. You’ve shown that $|V(G)|\ge 5$, and we know that $\delta(v)\ge 3$ for each $v\in V$ (since $G$ is $3$-connected), so $\sum_{v\in V}\delta(v)\ge 3\cdot 5=15$, contradicting the fact that $\sum_{v\in V}\delta(v)=2|E(G)|=14$. Therefore no such graph exists.