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 
.
![[asy] pair A=(0,90),B=(120,180),C=(120,120),D=(120,60),E=(120,0); pair F=(240,120),G=(240,60); draw(B--A--C); draw(D--A--E); dot(A); dot(B); dot(C); dot(D); dot(E); dot(F); dot(G); label("$A$",A,W); label("$B$",B,NW); label("$C$",C,NW); label("$D$",D,SW); label("$E$",E,SW); label("$F$",F,W); label("$G$",G,W); [/asy]](http://latex.artofproblemsolving.com/9/c/9/9c94e4dc9e9737eb24d98400740772f7ea272477.png)
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 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.
![[asy] pair A=(0,90),B=(120,180),C=(120,120),D=(120,60),E=(120,0); pair F=(240,120),G=(240,60); draw(B--A--C); draw(D--A--E); draw(B--F--G); real f(real x) { return -x^2/100+2.525x+90; }; path pft = graph(f, 0, 240); draw(pft); dot(A); dot(B); dot(C); dot(D); dot(E); dot(F); dot(G); label("$A$",A,W); label("$B$",B,NW); label("$C$",C,NW); label("$D$",D,SW); label("$E$",E,SW); label("$F$",F,W); label("$G$",G,W); [/asy]](http://latex.artofproblemsolving.com/6/f/8/6f8f24f0fb1fb00cadb77707be82db58b86c6cb3.png)
Similar to , 
also connects to 3 other vertices. If connects to 2 vertices from , then , , and the 2 vertices will again form a 4 way loop. However, if forms and edge with , 
will again be a 4-way loop. Thus, it's impossible to have form an edge with 2 other vertices without creating a 4-way loop.
