Be sure to review the exact meaning of path and cycle. The cycle
C
n
C
n
C, start subscript, n, end subscript is the graph with
V
=
{
1
,
…
,
n
}
V={1,…,n}V, equals, left brace, 1, comma, dots, comma, n, right brace and
E
=
{
{
1
,
2
}
,
{
2
,
3
}
,
…
,
{
n
−
1
,
n
}
,
{
n
,
1
}
}
E={{1,2},{2,3},…,{n−1,n},{n,1}}E, equals, left brace, left brace, 1, comma, 2, right brace, comma, left brace, 2, comma, 3, right brace, comma, dots, comma, left brace, n, minus, 1, comma, n, right brace, comma, left brace, n, comma, 1, right brace, right brace. A cycle in a graph
G
GG is a subgraph that is isomorphic to some
C
n
,
n
≥
3
C
n
,n≥3C, start subscript, n, end subscript, comma, n, is greater than or equal to, 3. So if
a
,
b
,
c
,
d
∈
V
a,b,c,d∈Va, comma, b, comma, c, comma, d, \in, V are all connected by edges, then
a
→
b
→
c
→
d
→
a
a→b→c→d→aa, right arrow, b, right arrow, c, right arrow, d, right arrow, a is a cycle, and
b
,
→
c
→
d
→
a
b,→c→d→ab, comma, right arrow, c, right arrow, d, right arrow, a is the same cycle (it corresponds to the same subgraph), but
a
→
c
→
b
→
d
a→c→b→da, right arrow, c, right arrow, b, right arrow, d is a different cycle.
Which of the following statements is true?
If
T
=
(
V
,
E
)
T=(V,E)T, equals, left parenthesis, V, comma, E, right parenthesis is a tree and
e
∈
(
V
2
)
∖
E
e∈(
2
V
)∖Ee, \in, start binomial, left parenthesis, V, over, 2, right parenthesis, end binomial, \setminus, E, then
T
+
e
T+eT, plus, e has exactly one cycle.
Let
G
=
(
V
,
E
)
G=(V,E)G, equals, left parenthesis, V, comma, E, right parenthesis be a graph and
e
∈
(
V
2
)
∖
E
e∈(
2
V
)∖Ee, \in, start binomial, left parenthesis, V, over, 2, right parenthesis, end binomial, \setminus, E, then
G
+
e
G+eG, plus, e has at most one more cycle than
G
GG.
Let
G
=
(
V
,
E
)
G=(V,E)G, equals, left parenthesis, V, comma, E, right parenthesis be a graph and
e
∈
(
V
2
)
∖
E
e∈(
2
V
)∖Ee, \in, start binomial, left parenthesis, V, over, 2, right parenthesis, end binomial, \setminus, E, then
G
+
e
G+eG, plus, e has at least one more cycle than
G
GG.
Let
T
=
(
V
,
E
)
T=(V,E)T, equals, left parenthesis, V, comma, E, right parenthesis be a tree and
e
∈
(
V
2
)
∖
E
e∈(
2
V
)∖Ee, \in, start binomial, left parenthesis, V, over, 2, right parenthesis, end binomial, \setminus, E be an edge. Let
f
ff be an edge on a cycle of
T
+
e
T+eT, plus, e. Is
(
T
+
e
)
−
f
(T+e)−fleft parenthesis, T, plus, e, right parenthesis, minus, f a tree?
1 point
Mathbot Says...
I wasn't able to parse your question, but the HE.NET team is hard at work making me smarter.