그래프 G (v, e)가 연결된 경우 $ | e | \ geq | v | -1 $

Question

그래프 G (v, e)가 연결된 경우 가장자리 수는 적어도 정점 -1의 수입니다. 당신이 그것에 대해 생각한다면 그것은 꽤 분명하지만 공식적으로 그것을 어떻게 증명합니까?

Answer 1

빈 그래프로 시작하는 프로세스를 상상해보십시오. 가장자리를 하나씩 추가하십시오.연결된 구성 요소의 수를 추적하십시오.처음에는 $ | v | $ 연결 구성 요소가 있습니다.추가 한 각 가장자리는 연결된 구성 요소 안에 속하거나 연결된 두 개의 연결된 구성 요소를 병합하고 연결된 구성 요소의 수를 최대 1시에 감소합니다. 따라서 $ | e |$ 가장자리, 연결된 구성 요소의 수는 적어도 $ | v |- | E | $ .그래프가 연결되어 있으면 $ | V |- | E |\ LEQ 1 $ , 그래서 $ |\ geq | v |- 1 $ .