|
In graph theory, a homeomorphism exists between two graphs G and G′ if there exists a graph H such that both G and G′ are subdivisions of that graph. If the edges of a graph are thought of as lines drawn from one vertex to another (as they are usually depicted in illustrations), then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the sense in which the term is used in topology. In general, a subdivision of a graph G is a graph resulting from the subdivision of edges in G. The subdivision of some edge e with endpoints yields a graph containing one new vertex v, and with an edge set replacing e by two new edges with endpoints and . For example, if we have the graph G1 subdividing edge x gives G1, and subdividing both x and y gives G2.
See also | ||||||||
|
| |||||||||
 |
|
| |