prove that .if a connected graph is decomposed into two subgraph g1 and g2 there must be at least one vertex common between g1 and g2 .what does decomposition mean
Answers
Step-by-step explanation:
A decomposition of a graph is a collection of edge-disjoint subgraphs of such that every edge of belongs to exactly one . If each is a path or a cycle in , then is called a path decomposition of . If each is a path in , then is called an acyclic path decomposition of . The minimum cardinality of a path decomposition (acyclic path decomposition) of is called the path decomposition number (acyclic path decomposition number) of and is denoted by () (()). In this paper we initiate a study of the parameter and determine the value of for some standard graphs. Further, we obtain some bounds for and characterize graphs attaining the bounds.
Decomposition of a graph means partitioning the vertices and edges of the graph into two or more subgraphs. In other words, we are breaking up the original graph into smaller subgraphs.
To prove that if a connected graph is decomposed into two subgraphs g1 and g2 there must be at least one vertex common between g1 and g2, we can use proof by contradiction.
Assume that there exists a connected graph G that can be decomposed into two subgraphs g1 and g2 such that there is no vertex common between them. This means that every vertex in G belongs to either g1 or g2, but not both.
Since G is connected, there must be at least one edge connecting vertices in g1 and vertices in g2. Without loss of generality, let (u, v) be such an edge, where u is in g1 and v is in g2.
Since every vertex in G belongs to either g1 or g2, and there is no vertex common between them, we can say that there is no path in g1 that connects u to v, and there is no path in g2 that connects v to u.
But this contradicts the fact that G is connected, which means that there must be a path between any two vertices in G. Therefore, our assumption that there exists a connected graph G that can be decomposed into two subgraphs g1 and g2 such that there is no vertex common between them is false.
Hence, we have proven that if a connected graph is decomposed into two subgraphs g1 and g2 there must be at least one vertex common between g1 and g2.
#SPJ3