Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

According to Diestel (page 4): "If $G' \subseteq G$ and $G'$ contains all the edges $xy \in E$ with $x, y \in V'$, then $G'$ is an induced subgraph of $G$"

According to Wikipedia "induced cycle is a cycle that is an induced subgraph of $G$; induced cycles are also called cordless cycles "

Does the definition by Diestel imply induced cycles are chordless?

In this graph, does induced subgraph $G[\{a,b,c,d\}]$ include edge $ac$?

Both $a$ and $c$ are in $V'$.

Graph $G$

share|improve this question

1 Answer 1

up vote 4 down vote accepted

Shortly, it does.

It is easier to think of induced subgraphs in terms of vertices: you take any $V' \subseteq V$ and take all the edges from $E$ that make sense, that is, both their ends are in $V'$. In fact, $(a,c) \in E$ and $a,c \in V'$ implies $(a,c) \in E'$.

I guess your confusion might be caused by the term "cycle" which has here two similar meanings:

  1. A closed path in a graph, i.e. a sequence $C = (c_0,\ldots,c_{n-1}) \subseteq V$ such that $(c_{i},c_{i+1}) \in E$ and $(c_{n-1},c_0) \in E$. Note that here, there may be many chords inside, and $C$ would still be a cycle.
  2. A graph that is a cycle. There are no other edges, in fact it is a connected 2-regular graph (i.e. connected and $\forall v.\ \mathrm{deg}(v) = 2$).

So a cycle-1 is chordless if and only if it is an induced cycle-2.

I hope it explained something ;-)

share|improve this answer
    
I read the Diestel book more carefully, and page 8 it says "An edge which joins two vertices of a cycle but is not itself an edge of the cycle is a chord of that cycle. Thus, an induced cycle in $G$, a cycle in $G$ forming an induced subgraph, is one that has no chords (Fig. 1.3.3)." Confusing ... –  Ohto Nordberg Feb 24 '13 at 11:20
    
@OhtoNordberg What is confusing you there? A cycle-1 in $G$ is induced if it is an induced cycle-2, that is, an induced subgraph that is a cycle-2. Such a cycle-1 cannot have chords, because then the induced subgraph would not be a cycle-2. –  dtldarek Feb 24 '13 at 20:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.