3
$\begingroup$

A connected graph $G$ has $100$ vertices and $199$ edges. Prove it is possible to delete all edges of a cycle in $G$ such that the remaining graph is still connected.

I have seen the thread on proving deleting one edge of a cycle in a connected graph $G$ results in a connected graph, but I don't believe the argument entirely applies in this case. I have made a few obvious observations. For example, after deleting every edge in the cycle, we know the part of the graph that has remained invariant is still connected, so we require at least one path from every vertex of this now deleted path to some vertex in the part of the graph that has remained untouched. Also, by Pigeonhole, at least one vertex will have degree $=1.$ I feel like all the progress I have so far along with the linked thread is extremely close to finishing the problem, but it's hard for me to formulate a rigorous proof. May I have some help? Thanks in advance.

$\endgroup$
2
  • 1
    $\begingroup$ So you need to prove that exists some circle $C$ such that after deleting it edges the $G\setminus C$ is still connected? $\endgroup$
    – nonuser
    Jul 8, 2023 at 8:10
  • $\begingroup$ This question is quite interesting. I have raised a more general question, see math.stackexchange.com/questions/4732616/… $\endgroup$
    – licheng
    Jul 8, 2023 at 8:42

2 Answers 2

6
$\begingroup$

Let $T$ be a spanning tree of $G$. Remove all the edges of $T$ from $G$. You will be left with a graph with $100$ vertices and $100$ edges which will necessarily contain a cycle (in general, a graph with $n$ vertices and $n$ edges contains a cycle). It's easy to see that removing this cycle from $G$ leaves it connected.

$\endgroup$
2
  • $\begingroup$ @nonuser Yes. you can even remove all the edges of $G\setminus T$ and the cycle is contained in it. $\endgroup$
    – licheng
    Jul 8, 2023 at 8:21
  • $\begingroup$ Very nice! .... $\endgroup$
    – nonuser
    Jul 8, 2023 at 8:25
0
$\begingroup$

No, this is not true. Consider three points A, B, C so that B and C are only connected in triangle ABC so other 97 points are connected to this triangle through A. Hence if you delete all edges of this cycle, B and C are no longer connected. Also the resulting G' is not connected.

Note: if you only deleted one of the edge of triangle, G' is still connected.

$\endgroup$
3
  • 6
    $\begingroup$ It says "it is possible to delete all edges of a cycle"... i.e., maybe in your example there is another cycle (not $ABC$) that can be deleted? $\endgroup$
    – user700480
    Jul 8, 2023 at 8:01
  • 1
    $\begingroup$ then it will be the case the other answer discussed. $\endgroup$
    – Learner
    Jul 8, 2023 at 8:21
  • 2
    $\begingroup$ There is no case that the other answer didn't discuss. A tree on $n$ nodes has $n-1$ edges. Any connected graph has a spanning tree, so this graph has a tree connecting to all nodes with $99$ edges. The remaining $100$ edges can be removed without disconnecting the graph. Those $100$ edges have one too many edges to form a tree, so they must include a cycle. $\endgroup$ Jul 8, 2023 at 16:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .