이산수학(그래프이론)에서 그래프 동형과 관련하여 질문 드립니다.

[munhwalove]

제가 이산수학(박종안)책에서 읽기로는
그래프의 꼭짓점의 수가 많아지면 두 그래프가 동령인지 아닌지를 결정하는 것은 현재까지도 효과적인 방법이 알려져 있지 않은 어려운 문제
라고 합니다.




그런데 혹시 꼭짓점의 수가 몇개 이하일때 다음과 같은 명제가 성립하는지 알고 있는 분 있으신가요?



'어떤 그래프 G가 simple connected graph(단순연결그래프)라고 하자. 그래프 G의 vertex(꼭짓점)의 degree(차수)의 집합이 같은 그래프들은 전부 동형이다'



위의 명제가 좀 난잡하게 써 있죠?; 위 명제에 대한 예를 들자면 꼭짓점의 갯수가 5개인 그래프에 대해 각 꼭짓점들의 차수의 집합이 {1,1,2,3,3}인 모든 그래프는 서로 동형이다. 라는 겁니다. 좀 설명이 되었는지 모르겠네요;;



꼭짓점의 수가 4개일 경우는 위 명제가 성립하는 거 같고요(단순연결이 아닌 단순그래프이기만 해도 성립하는 듯) 꼭짓점의 수가 5개일 경우도 제가 일일이 해보니까 위 명제가 성립하는 거 같더라고요.
분명히 꼭짓점의 수가 늘어나면 성립안하는 예가 있을 텐데 최초로 성립하지 않는 최소 꼭짓점의 수가 궁금합니다. 즉, 위 명제가 꼭짓점의 수가 몇 개 일때 까지 성립하는지 궁금하네요ㅎㅎ

[munhwalove]

혹시 이 글을 많이 늦게 보셨더라도 괜찮으니 늦게라도 답변해 주시면 정말 감사드리겠습니다:D