Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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. :)

share|cite|improve this question
up vote 2 down vote accepted

(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$.

share|cite|improve this answer
Thank you for your response, but may I ask for your clarification on (2)? My thought is that if I have a vertex, say A, of degree 2, then there are exactly 2 edges incident to A. And if I have a vertex, say C, of degree 3, then there are exactly 3 edges incident to C. But how should I connect A and C ? Can you give an example of a picture which will do the job? I'm thinking about A --> B --> C --> D --> E --> A, but I feel something isn't quite right. Thank you – Cecile Nov 11 '12 at 23:58
@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$. – Brian M. Scott Nov 12 '12 at 16:33

Your Answer


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.