Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 $\frac{7\cdot 3}{2}$, which isn't an integer. Therefore, at least one vertex has a minimal degree of 4.

WLOG, let $A$ be the vertex with a degree of 4 or more. $A$ must be connected to at least 4 other vertices, name them $B$, $C$, $D$, and $E$, and name the set that contains these 4 vertices $S$.

[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]

$F$ has a degree of 3 or more. If $F$ is connected to at least 2 elements from set $S$, then $A$, $F$, and these 2 vertices will form a loop with 4 elements. For example, if $F$ is connected to $B$ and $C$, then $A-B-F-C-A$ will form a loop.

The only way for $F$ to connect to 3 other vertices without forming a 4-vertices loop is by having an edge between $FG$, an edge between $AF$, and an edge between $F$ and one of the vertices from set $S$. WLOG, let $FB$ 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]

Similar to $F$, $G$ also connects to 3 other vertices. If $G$ connects to 2 vertices from $S$, then $A$, $G$, and the 2 vertices will again form a 4-vertices loop. However, if $G$ forms an edge with $A$, $A-B-F-G-A$ will again be a 4-vertices loop. Thus, it's impossible to have $G$ form an edge with 2 other vertices without creating a 4-vertices loop.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_Indonesia_MO_Problems/Problem_4&oldid=227494"