Hi! I need help with verifying this exercise and clarifying a doubt. I might tell you the definition I have since I'm translating and I don't know if with the translation I get the same terms in English.
The exercise says:
a. Find all the proper paths (paths) that go from vertex A to vertex F.
Proper path – is when all vertices are different. Every proper path is a simple path.
So this is what I got: ${(A,B,C,F), (A,B,C,E,F), (A,B,E,F), (A,B,E,C,F), (A,D,E,F), (A,D,E,C,F), (A,D,E,B,C,F)}$
b. Find all the simple paths (trails) that go from A to F.
Simple path (trail) – is when all the arcs are different.
${(A,B,C,F), (A,B,C,E,F), (A,B,E,F), (A,B,E,C,F), (A,D,E,F), (A,D,E,C,F), (A,D,E,B,C,F), (A,D,E,B,C,E,F)}$
c. Find the distance from A to F.
Distance – the shortest length between two vertices.
So the distance is 3.
d. The diameter of the graph.
Diameter – the maximum of the distance between the vertices of the graph.
So diameter is 5.
e. Find the subgraphs obtained by removing each of its vertices. Are there cut points in that graph (a cut point in a connected graph is that one that when eliminated, together with all its incident edges, gives rise to a not connected graph)?
EDITED: Are these all?
Thanks for the help.
Best Answer
From the comments it looks like you got a bit confused for the definitions of diameter and distance.
The diameter is not the maximum path length between any two vertices. The diameter of the graph is the maximum distance between any two vertices. And the distance between two vertices is the length of the shortest path.
Given the shortest path $ABCF$, the distance between $A$ and $F$ is 3, and this is fixed. Even if there exist longer paths such as $ADEBCF$, the distance is still 3. We can reach $F$ from $A$ in 3 steps. Therefore the eccentricity of $A$ is $3$, not $5$.
The diameter is a max/min value. If $V$ is our set $\{A,B,C,D,E,F\}$ $$ diam = \max_{x,y\in V} \{distance(x,y)\}$$ $$ diam = \max_{x,y\in V} \{\min_{path(x\to y) }length(path)\}$$
The distance between $A$ and $F$ is fixed at 3, so we know that $diam\geq 3$. In order to find the diameter of the graph, you need to check the distance between all other pairs of vertices. It is easy to see that for any other pair of vertices the distance is less than 3. Therefore $$diam = 3$$
Regarding the last question : when you remove a vertex, you remove all the edges that "end" at this vertex (we say all edges incident with this vertex). For example if you remove the vertex $A$, you get the following subgraph.
I'm sure you can finish from here.