设无向图G包含n个顶点和m条边,且G的连通分量个数为k。若G中存在一条边(u, v),使得删除该边后G的连通分量个数变为k+1,且添加该边后G的连通分量个数变为k-1,则下列哪项一定成立?
答案解析
**A. 正确**
根据连通分量的定义,如果u和v属于同一个连通分量,那么删除边(u, v)后连通分量个数不会增加,添加边(u, v)后连通分量个数不会减少。
**B. 错误**
如果u和v属于同一个连通分量,那么删除边(u, v)后连通分量个数不会增加,添加边(u, v)后连通分量个数不会减少。
**C. 错误**
删除边(u, v)后,u和v所在的连通分量会分离,因此连通分量个数增加1。不存在边(x, y)使得删除后连通分量个数增加2。
**D. 错误**
根据连通分量的定义,如果G中不存在边(x, y)使得删除后连通分量个数增加2,那么G一定是连通的,与题设矛盾。
正确答案:A