[대학교이상] 수형도 문제인데 너무 복잡해보임.. 도와주실분!..?

[육토리(kjhoon2002)]

꼭짓점의 개수가 315개인 수형도에 길이가 6인 경로가 없을 때, 이 수형도에 차수가 14이상인 꼭짓점이 있음을 보이시오

어떻게 시작할지 감도 안잡히는데.. 어떻게 하면 좋을까?

- dc official App

[익명(211.234)]

개허수들만 있는 톡방만 돌아댕기다 결국 여까지오노ㅋㅋ

[육토리(kjhoon2002)]

ㅜㅜㅜ - dc App

[육토리(kjhoon2002)]

힌트라도 던져줘 - dc App

[익명(118.235)]

최대 경로의 길이가 5일때, 이 경로의 점을 1,2,3,4,5라 하면, 1,5는 leaf고, 2,3,4에 점을 연결할 수 있음. 길이 5인 경로가 최대니까 2,4에는 한칸씩만 연결할수있고, 차수 14인 점이 없도록 하려면 최대 2*11=22개의 변을 추가할 수 있음.

[육토리(kjhoon2002)]

점이 6개여야 하는 거 아님?-? - dc App

[익명(118.235)]

아 미안 점 6개로 해서 똑같이 하면 (가운데 두개 11*12)총합 314 나와서 모순임 어쩐지 숫자가 너무 남더라

[육토리(kjhoon2002)]

감샇감사 ㅎㅎ - dc App

[익명(118.235)]

가운데 점에는 우선 11개의 점을 연결하고, 그 점들에 각각 12개 점들 연결하면 11+11*12=143개의 점들을 추가할 수 있음. 5+22+11+11*12=170<315 조건을 만족하면서 최대 점을 갖는 그래프의 점 개수가 315보다 작으므로 모순이고, 차수 14이상인 점 존재