PROBLEM LINK: Problem
Author and editorialist: Denis Anishchenko
Tester: Hasan Jaddouh
DIFFICULTY: Medium
PREREQUISITES: Constructive, graphs
EXPLANATION:
Let’s consider vertex v with minimal degree (degree is number of neighbors). If degree(v) < k, than we have found a good cut: we can choose A = \{v\}. Otherwise, for all vertices v is true that degree(v) \geq k. Let’s go from vertex v in neighbor u, if it’s not visited earlier, after that, go from u to not visited vertex w and so on. In some moment we will have the situation that all neighbors of some vertex f is visited earlier, let’s consider neighbor which we have visited earlier than another ones (u). It’s clear that path between u and f through visited vertices and edge (u, v) forms a correct simple cycle.