Self-intersecting graph
Source: Iranian National Olympiad (3rd Round) 2008
September 20, 2008
combinatorics proposedcombinatorics
Problem Statement
A graph is called a self-intersecting graph if it is isomorphic to a graph whose every edge is a segment and every two edges intersect. Notice that no edge contains a vertex except its two endings.
a) Find all 's for which the cycle of length is self-intersecting.
b) Prove that in a self-intersecting graph .
c) Find all self-intersecting graphs.
http://i35.tinypic.com/x43s5u.png