<p>No, no such graph exists. To see why not, suppose we have a circle graph defined by a triangle-free set of chords. Let $n$ be the number of vertices of the circle graph (or the number of chords), and $m$ be the number of edges of the graph (crossings of two chords). Then an easy induction on the number of chords shows that the arrangement of the chords has exactly $m+n+1$ faces. However, there are at most $2n$ faces that touch the circle (fewer if some faces touch the circle more than once), so if $m&gt;n$ then there must be at least two interior faces of the arrangement. Let $p$ be any shortest path in the dual graph of the arrangement (a <a href="http://en.wikipedia.org/wiki/Squaregraph">squaregraph</a>) from one such face to another, and let $c$ be any chord dual to an edge of $p$. Then the star-cutset induced by $c$ separates some of the chords bounding the face at one end of $p$ from some of the chords bounding the face at the other end.</p>

CC BY-SA 3.0
2013-06-27T04:26:43.987Z
2013-06-27T04:32:33.723Z
2013-06-27T04:32:33.723Z
David Eppstein
<p>Suppose $G$ is a triangle-free star-cutset-free circle graph.
I will show that $G$ contains no vertex with degree more than 2. Therefore, $G$ has at most $n$ edges.</p>

<p>Consider a circle representation $C$ of $G$. A set of chords is <em>parallel</em> if no two of them cross but there is a line crossing all the chords.</p>

<p><strong>Property 1</strong>: $C$ has no 3 parallel chords.</p>

<p><strong>Proof</strong>. Suppose $C$ has 3 parallel chords. Condider the vertex $v$ corresponding to the middle chord. Then, $N[v]$ is a cutset. This proves the property.</p>

<p>For the sake of contradiction, assume $G$ has a vertex $v$ of degree at least 3. Then, the chord corresponding to $v$ intersects 3 other chords. Since these 3 chords intersect one line, they are either parallel or two of them intersect. Due to Property 1, two of them intersect, which means their vertices form a triangle with $v$, which contradicts $G$ being triangle-free.</p>

CC BY-SA 3.0
2013-06-27T04:37:53.963Z
I don't think propety 1 is true. Consider chords forming the sides of a regular $n$-gon, with the circle slightly bigger so that it contains the $n$-gon but does not contain any other crossings of those sides.
David Eppstein
CC BY-SA 3.0
2013-06-27T05:03:11.863Z
Ok, as corrected I think this works, and is simpler than my proof.
David Eppstein
CC BY-SA 3.0
2013-06-27T04:31:22.803Z
2013-06-27T04:48:50.260Z
2013-06-27T04:48:50.260Z
Serge Gaspers
<p>I'm trying to find a graph with those properties for my studies, but unfortunately I can't find such graph.</p>

<p>Does anyone know if there is that graph, or why is it impossible to exist?</p>

CC BY-SA 3.0
2013-06-27T03:16:50.510Z
Can you explain your terminology? What is "star-cutset-free" and what is "circle graph"?
Yuval Filmus
CC BY-SA 3.0
2013-06-27T03:45:08.290Z
Sure. =)

A circle graph is a graph (undirected) whose vertices can be associated with chords in a circle such that two vertices are adjacent iff the corresponding chords cross each other. Here is an image as example (from Wikipedia): http://en.wikipedia.org/wiki/File:Circle_graph.svg

And we can say a graph has a star-cutset when you have a vertex v such that removing v and its neighbours (N[v]) from the graph turns it disconnected.
Rafael Oliveira Lopes
CC BY-SA 3.0
2013-06-27T03:45:13.153Z
[ISGCI](http://www.graphclasses.org/index.html) has definitions of [triangle-free](http://www.graphclasses.org/classes/gc_371.html) and [circle graph](http://www.graphclasses.org/classes/gc_132.html).  A star-cutset is a subset $S$ of vertices that separates the graph, such that one vertex in $S$ is adjacent to every other vertex in $S$.
Jeffε
CC BY-SA 3.0
2013-06-27T03:49:42.250Z
[This paper](http://arxiv.org/abs/1007.0804) may be relevant.
Jeffε
<graph-theory><graph-classes>
Is there any triangle-free, star-cutset-free, circle graph, with more than n edges?
Rafael Oliveira Lopes
# Is there any triangle-free, star-cutset-free, circle graph, with more than n edges?

(Asked by: username_0 on 2013-06-27)

I'm trying to find a graph with those properties for my studies, but unfortunately I can't find such graph.

Does anyone know if there is that graph, or why is it impossible to exist?

**Tags:** graph-theory, graph-classes

> **Comments:**
> **username_1**: Can you explain your terminology? What is "star-cutset-free" and what is "circle graph"?  
> **username_0**: Sure. =)  A circle graph is a graph (undirected) whose vertices can be associated with chords in a circle such that two vertices are adjacent iff the corresponding chords cross each other. Here is an image as example (from Wikipedia): http://en.wikipedia.org/wiki/File:Circle_graph.svg  And we can say a graph has a star-cutset when you have a vertex v such that removing v and its neighbours (N[v]) from the graph turns it disconnected.  
> **username_2**: [ISGCI](http://www.graphclasses.org/index.html) has definitions of [triangle-free](http://www.graphclasses.org/classes/gc_371.html) and [circle graph](http://www.graphclasses.org/classes/gc_132.html).  A star-cutset is a subset $S$ of vertices that separates the graph, such that one vertex in $S$ is adjacent to every other vertex in $S$.  
> **username_2**: [This paper](http://arxiv.org/abs/1007.0804) may be relevant.  

---

## 2 answers

### Answer by username_4 on 2013-06-27. Score: 12 | Accepted answer

Suppose $G$ is a triangle-free star-cutset-free circle graph.
I will show that $G$ contains no vertex with degree more than 2. Therefore, $G$ has at most $n$ edges.

Consider a circle representation $C$ of $G$. A set of chords is *parallel* if no two of them cross but there is a line crossing all the chords.

**Property 1**: $C$ has no 3 parallel chords.

**Proof**. Suppose $C$ has 3 parallel chords. Condider the vertex $v$ corresponding to the middle chord. Then, $N[v]$ is a cutset. This proves the property.

For the sake of contradiction, assume $G$ has a vertex $v$ of degree at least 3. Then, the chord corresponding to $v$ intersects 3 other chords. Since these 3 chords intersect one line, they are either parallel or two of them intersect. Due to Property 1, two of them intersect, which means their vertices form a triangle with $v$, which contradicts $G$ being triangle-free.

> **Comments:**
> **username_3**: I don't think propety 1 is true. Consider chords forming the sides of a regular $n$-gon, with the circle slightly bigger so that it contains the $n$-gon but does not contain any other crossings of those sides.  
> **username_3**: Ok, as corrected I think this works, and is simpler than my proof.  

---

### Answer by username_3 on 2013-06-27. Score: 9

No, no such graph exists. To see why not, suppose we have a circle graph defined by a triangle-free set of chords. Let $n$ be the number of vertices of the circle graph (or the number of chords), and $m$ be the number of edges of the graph (crossings of two chords). Then an easy induction on the number of chords shows that the arrangement of the chords has exactly $m+n+1$ faces. However, there are at most $2n$ faces that touch the circle (fewer if some faces touch the circle more than once), so if $m>n$ then there must be at least two interior faces of the arrangement. Let $p$ be any shortest path in the dual graph of the arrangement (a [squaregraph](http://en.wikipedia.org/wiki/Squaregraph)) from one such face to another, and let $c$ be any chord dual to an edge of $p$. Then the star-cutset induced by $c$ separates some of the chords bounding the face at one end of $p$ from some of the chords bounding the face at the other end.


---

