2
$\begingroup$

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$
  • 1
    $\begingroup$ It means that $G$ itself has the property, but if you add a new edge to $G$ then it will no longer have the property. $\endgroup$ – bof Jan 27 '17 at 10:10
7
$\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$
  • 1
    $\begingroup$ This is definitely a concept best explained using examples in my opinion. $\endgroup$ – Arthur Jan 27 '17 at 10:07
  • $\begingroup$ Yes, even better explained using pictures. $\endgroup$ – wordsforthewise Jun 22 '17 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.