Difference between revisions of "2009 Indonesia MO Problems/Problem 4"
Victorzwkao (talk | contribs) (Created page with "==Solution== Suppose that among the 7 vertices, each has a degree of 3. Then the total amount of edges will be <math>\frac{7\cdot 3}{2}</math>, which isn't an integer. Theref...") |
Victorzwkao (talk | contribs) (→Solution) |
||
Line 26: | Line 26: | ||
</asy> | </asy> | ||
− | <math>F</math> has a degree of 3 or more. If <math>F</math> is connected to at least 2 elements from set <math>S</math>, then | + | <math>F</math> has a degree of 3 or more. If <math>F</math> is connected to at least 2 elements from set <math>S</math>, then <math>A</math>, <math>F</math>, and these 2 vertices will form a loop with 4 elements. For example, if <math>F</math> is connected to <math>B</math> and <math>C</math>, then <math>A-B-F-C-A</math> will form a loop. |
The only way for <math>F</math> to connect to 3 other vertices is by having an edge between <math>FG</math>, an edge between <math>AF</math>, and an edge between <math>F</math> and one of the vertices from set <math>S</math>. WLOG, let <math>FB</math> be the edge. | The only way for <math>F</math> to connect to 3 other vertices is by having an edge between <math>FG</math>, an edge between <math>AF</math>, and an edge between <math>F</math> and one of the vertices from set <math>S</math>. WLOG, let <math>FB</math> be the edge. |
Revision as of 10:17, 18 September 2024
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 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 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.