2009 Indonesia MO Problems/Problem 4
Solution
Suppose that among the 7 vertices, each has a degree of 3. Then the total amount of edges will be , which isn't an integer. Therefore, at least one vertex has a minimal degree of 4.
WLOG, let be the vertex with a degree of 4 or more.
must be connected to at least 4 other vertices, name them
,
,
, and
, and name the set that contains these 4 vertices
.
has a degree of 3 or more. If
is connected to at least 2 elements from set
, then
,
, and these 2 vertices will form a loop with 4 elements. For example, if
is connected to
and
, then
will form a loop.
The only way for to connect to 3 other vertices without forming a 4-vertices loop is by having an edge between
, an edge between
, and an edge between
and one of the vertices from set
. WLOG, let
be the edge.
Similar to ,
also connects to 3 other vertices. If
connects to 2 vertices from
, then
,
, and the 2 vertices will again form a 4-vertices loop. However, if
forms an edge with
,
will again be a 4-vertices loop. Thus, it's impossible to have
form an edge with 2 other vertices without creating a 4-vertices loop.