connectivity of a simple graph with given degrees.

65 Views Asked by At

I recenty encountered an exercise that describes the simple graph $G(V, E)$ as being $3$-regular, of order $6$, that is - it has $6$ vertices of degree $3$. No other details are given at this point.

One question asks to prove that the graph is connected, and the listed answer simply draws such a graph, and comments that it is connected.

My question is whether such an answer can be considered as rigorous and whether it could be accepted in an exam, and if not, how you would answer it.

1

There are 1 best solutions below

1
On BEST ANSWER

To answer the edited question, no this is not a valid proof as the existence of a connected graph with these properties doesn't rule out the possibility of a disconnected graph also existing. You could give both the possible graphs (there are only two) and show they are both connected, but showing there are only two is probably harder than the original question.

Here's how I would do the question. Take any two vertices. If there is no edge between them, they each have $3$ neighbours out of the remaining $4$ vertices, so they must have a neighbour (in fact, at least two) in common. So for any two vertices there is a path of length $1$ or $2$ between them, so the graph is connected.

(Answer to a previous version with a typo)

There is no $3$-regular graph with $9$ vertices. By the handshaking lemma, the sum of the vertex degrees ($27$) is twice the number of edges. But you can't have $13.5$ edges.

If you change the question to ask about, say, a $3$-regular graph with $8$ vertices, then this would not be a valid proof. You can draw a $3$-regular $8$-vertex connected graph (e.g. the cube), but you can also have a disconnected graph (two tetrahedra).