That is if H is a Minor of a graph G through any property of H can we conclude G as Eulerian if it is under certain conditions.
Minor of a graph G is obtained by contracting the edges of G. But eulerian graph is a graph with all the vertices of even degree. There is no connection in between them.
Does the Eulerian nature has a hereditary property on the number contractions we make and the type of graph we take under certain condition only i mean.
Like minors of planar graphs are always planar.
There is an if and only if condition
If all vertices of a connected graph are of even degree if and only if it contains a Euler circuit. In term the graph is Eulerian.
As far a edge contraction we mean merging the two nodes at either end of an edge then remove the self loop's and multiple edges we can even put two non-adjacent vertices too.
If we contract an edge e=uv of a graph G, its end vertices are identified to get a new vertex w. The vertex w adjacent to a vertex of G in the contracted graph, if that vertex is adjacent to either u or v in G. More over, w is the only vertex in the contracted graph that is not in G. If G is an Eulerian graph, then all vertices of G have even degree. Therefore, in the contracted graph, the vertex w also have even degree. Therefore, the minor of a graph is also Eulerian.
- Badges
- Science topic
- Similar topics
- Mathematics