Going through Graph theory , i found
We call Graph $G$ edge Maximal if with a given graph property if $G$ itself has the property but no graph $G$+$xy$ does for non adjacent vertices $x,y$ $\epsilon$ G
I am not getting what does it really mean .!
please help me out !!!
$\endgroup$ 11 Answer
$\begingroup$A graph with a certain property is called edge maximal for that property if you cannot add another edge but keep the property. For instance, a tree is an edge-maximal cycle-free graph. You cannot add an edge while keeping it cycle-free, because adding an edge to a tree always adds a cycle. Similarly, if you graph consists of two components, each of which is a complete graph, then this graph is edge maximal disconnected: adding any edge to the graph turns it into a connected graph.
$\endgroup$ 2
