2
$\begingroup$

I'm studying basic graph theory, and my instructor gives me these statements to translate into pictures. I don't quite understand the meanings of the statements, but I have some thoughts about them.

1/ "Any two vertices a, b are connected by at least 2 distinct paths of length 4"

$\Longrightarrow$ Does this mean that any two vertices $a$, $b$ are connected by at least 1 path of length 8?

2/ "Any vertex of degree 2 is connected by a path of length 3 with a vertex of degree 3" $\Longrightarrow$ what does this mean ? (in terms of a picture)

I'm thinking about a picture of 5 vertices $A$, $B$, $C$, $D$, $E$, where $A \longrightarrow B$ and $A \longrightarrow C$ but $B \longrightarrow D$ and $C \longrightarrow D$ and $E \longrightarrow D$ and $E$ doesn't connect with $A$. Is this idea right ?

3/ " Any 2 vertices connected by a path of length 3 have degree at most 2"

$\Longrightarrow$ Is this statement saying something about the "diagonal" ? Because I'm thinking about a picture of 4 vertices $A$, $B$, $C$, $D$ where $A \longrightarrow B$ and $B \longrightarrow C$ and $C \longrightarrow D$. So $A$ and $D$ have degree at most 2 when I connect $C$ with $A$ and $B$ with $D$.

Would you please help me on these questions? Thank you in advance. :)

1 Answers 1

2

(1) No, it means that for any two distinct vertices $a$ and $b$ there are at least two different paths from $a$ to $b$, each of length $4$. If they’re disjoint, that means that the graph contains a circuit of length $8$ with $a$ and $b$ as far apart on the circuit as possible. HINT: Think of an octagon.

(2) This won’t quite work. The vertices of degree $2$ are $A,B$, and $C$, and the vertex of degree $3$ is $E$. $B$ and $C$ are connected to $E$ by paths of length $3$ (and also by paths of length $1$), but $A$ is not: both paths from $A$ to $E$ are of length $2$. Your graph can be drawn as a square with a ‘sticker’ at one corner ($D$) leading to $E$; what if you add another sticker like that at $A$, going to a new vertex $F$?

(3) Your graph is find before you add edges between $A$ and $C$ and between $B$ and $D$. The graph looks like this:

                A --- B --- C --- D 

The only vertices connected by a path of length $3$ are $A$ and $D$, and sure enough, they have degree at most $2$. ‘At most $2$’ is the same as $\le 2$. In fact, adding those two extra edges ruins the example, because then you have the path $BACD$ of length $3$ from $B$ to $D$, and yet $\deg B=3\not\le 2$.

  • 0
    @Cecile: No, a circuit of five vertices won’t do the job. I’m not sure how that relates to what I suggested for (2), though, which was to take the graph that you originally had for (2) and add one more vertex connected to $A$.2012-11-12