Rabbit_Alex
New member
- Joined
- Jan 23, 2007
- Messages
- 2
Hi there, this is my first post. I signed up because I need help with my Formal Models of Computation class, which is a continuation of Discrete Math/Structures that I struggled through last semester.
Here is my problem.
Let the graph G = (V, E), where V is the set of all vertices in the graph, and E is the set of all edges in the graph. If there is a walk between vertex v1 which exists in V, and vertex v2 which exists in V, then there must be a path whose length is no larger than |V| - 1 (the number of vertices minus 1), between the two vertices. I underlined walk and path because I think they are important for solving the proof.
What I have so far.
I am trying to argue that any graph is composed of "sub-graphs" which fit into categories like wheel graph, complete bipartite graph, circle graph, etc. The path length between any two vertices in these types of graph is always less than |V| - 1. Since any graph will be made of subgraphs which have this property, it must be true for all graphs. So far all I have are some pictures of different types of graphs showing how this property is true for all of them. What I need is a way to combine them into a general proof for all graphs.
I am assuming that my reasoning is completely wrong.
Sorry about the long post. Thank you for any help.
Here is my problem.
Let the graph G = (V, E), where V is the set of all vertices in the graph, and E is the set of all edges in the graph. If there is a walk between vertex v1 which exists in V, and vertex v2 which exists in V, then there must be a path whose length is no larger than |V| - 1 (the number of vertices minus 1), between the two vertices. I underlined walk and path because I think they are important for solving the proof.
What I have so far.
I am trying to argue that any graph is composed of "sub-graphs" which fit into categories like wheel graph, complete bipartite graph, circle graph, etc. The path length between any two vertices in these types of graph is always less than |V| - 1. Since any graph will be made of subgraphs which have this property, it must be true for all graphs. So far all I have are some pictures of different types of graphs showing how this property is true for all of them. What I need is a way to combine them into a general proof for all graphs.
I am assuming that my reasoning is completely wrong.
Sorry about the long post. Thank you for any help.