TITLE: If we have a connected graph that remains connected after removing any edge, can we make the following claim
QUESTION [0 upvotes]: Given we have a connected graph $G$ that remains connected if any edge in $G$ is removed
Say we have $(a, b) \in E(G)$ (where $E(G)$ is the set of all edges in $G$) and $(c, d) \in E(G)$.
Can we assume that $(a, d) \in E(G)$? I would assume no because the graph can be still be connected if an edge from $(a, d)$ doesn't exist.

REPLY [1 votes]: Any cycle graph serves as a counterexample to your claim.
Take for instance a cycle with four nodes in the order $a$, $b$, $d$, $c$. It contains edges $(a,b)$ and $(c,d)$, but not $(a,d)$. So you are correct that the assumption does not hold.
{"set_name": "stack_exchange", "score": 0, "question_id": 3725692}