# Revision history [back]

The graphs with a given property (provided by the lambda function) are constructed by recurrence (see the augment parameter in the doc). The problem you are facing is that having maximal degree at least two is not preserved by removing an edge. In particular, the graph on 5 vertices with no edges does not have this property, hence no larger graph can be constructed from this one, which explains why you do not get any graph in your first construction.

A possible workaround is to actually filter among all graphs of size 5:

sage: L = [G for G in graphs(5) if max(G.degree()) >= 2]
sage: len(L)
31


Of course, it is not speed-efficient since you have to look at all graphs.

The graphs with a given property (provided by the lambda function) are constructed by recurrence (see the augment parameter in the doc). The problem you are facing is that having maximal degree at least two is not preserved by removing an edge. In particular, the graph on 5 vertices with no edges does not have this property, hence no larger graph can be constructed from this one, which explains why you do not get any graph in your first construction.

A possible workaround is to actually filter among all graphs of size 5:

sage: L = [G for G in graphs(5) if max(G.degree()) >= 2]
sage: len(L)
31


Of course, it is not speed-efficient in general since you have to look at all graphs.

graphs. In your case it is not a problem since almost all graphs have your property.

Another workaround is to notice that the condition max(G.degree()) >= 2] on G is equivalent to the condition min(G.degree()) <= 2] on G.complement(), and this latter condition is hereditary:

sage: M = [G.complement() for G in graphs(5, lambda G: min(G.degree()) <= 2)]
sage: len(M)
31


Of course, you will not see much speed difference in this case, but it can matter for classes of graphs with smaller density among all graphs:

sage: %timeit L = [G for G in graphs(7) if max(G.degree()) >= 5]
1 loops, best of 3: 11.7 s per loop
sage: %timeit M = [G.complement() for G in graphs(7, lambda G: min(G.degree()) <= 1)]
1 loops, best of 3: 5.84 s per loop


The graphs with a given property (provided by the lambda function) are constructed by recurrence (see the augment parameter in the doc). The problem you are facing is that having maximal degree at least two is not preserved by removing an edge. In particular, the graph on 5 vertices with no edges does not have this property, hence no larger graph can be constructed from this one, which explains why you do not get any graph in your first construction.

A possible workaround is to actually filter among all graphs of size 5:

sage: L = [G for G in graphs(5) if max(G.degree()) >= 2]
sage: len(L)
31


Of course, it is not speed-efficient in general since you have to look at all graphs. In your case it is not a problem since almost all graphs have your property.

Another workaround is to notice that the condition max(G.degree()) >= 2]2 on G is equivalent to the condition min(G.degree()) <= 2]2 on G.complement(), and this latter condition is hereditary:

sage: M = [G.complement() for G in graphs(5, lambda G: min(G.degree()) <= 2)]
sage: len(M)
31


Of course, you will not see much speed difference in this case, but it can matter for classes of graphs with smaller density among all graphs:

sage: %timeit L = [G for G in graphs(7) if max(G.degree()) >= 5]
1 loops, best of 3: 11.7 s per loop
sage: %timeit M = [G.complement() for G in graphs(7, lambda G: min(G.degree()) <= 1)]
1 loops, best of 3: 5.84 s per loop


The graphs with a given property (provided by the lambda function) are constructed by recurrence (see the augment parameter in the doc). The problem you are facing is that having maximal degree at least two is not preserved by removing an edge. In particular, the graph on 5 vertices with no edges does not have this property, hence no larger graph can be constructed from this one, which explains why you do not get any graph in your first construction.

A possible workaround is to actually filter among all graphs of size 5:

sage: L = [G for G in graphs(5) if max(G.degree()) >= 2]
sage: len(L)
31


Of course, it is not speed-efficient in general since you have to look at all graphs. In your case it is not a problem since almost all graphs have your property.

Another workaround is to notice that the condition max(G.degree()) max(H.degree()) >= 2 on Gfor H=G is equivalent to the condition min(G.degree()) min(H.degree()) <= 2 on G.complement()for H=G.complement(), and this latter condition is hereditary:

 sage: M = [G.complement() for G in graphs(5, lambda G: min(G.degree()) <= 2)] sage: len(M) 31 Of course, you will not see much speed difference in this case, but it can matter for classes of graphs with smaller density among all graphs: sage: %timeit L = [G for G in graphs(7) if max(G.degree()) >= 5] 1 loops, best of 3: 11.7 s per loop sage: %timeit M = [G.complement() for G in graphs(7, lambda G: min(G.degree()) <= 1)] 1 loops, best of 3: 5.84 s per loop 




 Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license. about | faq | help | privacy policy | terms of service Powered by Askbot version 0.7.59 Please note: Askbot requires javascript to work properly, please enable javascript in your browser, here is how //IE fix to hide the red margin var noscript = document.getElementsByTagName('noscript')[0]; noscript.style.padding = '0px'; noscript.style.backgroundColor = 'transparent'; askbot['urls']['mark_read_message'] = '/s/messages/markread/'; askbot['urls']['get_tags_by_wildcard'] = '/s/get-tags-by-wildcard/'; askbot['urls']['get_tag_list'] = '/s/get-tag-list/'; askbot['urls']['follow_user'] = '/followit/follow/user/{{userId}}/'; askbot['urls']['unfollow_user'] = '/followit/unfollow/user/{{userId}}/'; askbot['urls']['user_signin'] = '/account/signin/'; askbot['urls']['getEditor'] = '/s/get-editor/'; askbot['urls']['apiGetQuestions'] = '/s/api/get_questions/'; askbot['urls']['ask'] = '/questions/ask/'; askbot['urls']['questions'] = '/questions/'; askbot['settings']['groupsEnabled'] = false; askbot['settings']['static_url'] = '/m/'; askbot['settings']['minSearchWordLength'] = 4; askbot['settings']['mathjaxEnabled'] = true; askbot['settings']['sharingSuffixText'] = ''; askbot['settings']['errorPlacement'] = 'after-label'; askbot['data']['maxCommentLength'] = 800; askbot['settings']['editorType'] = 'markdown'; askbot['settings']['commentsEditorType'] = 'rich\u002Dtext'; askbot['messages']['askYourQuestion'] = 'Ask Your Question'; askbot['messages']['acceptOwnAnswer'] = 'accept or unaccept your own answer'; askbot['messages']['followQuestions'] = 'follow questions'; askbot['settings']['allowedUploadFileTypes'] = [ "jpg", "jpeg", "gif", "bmp", "png", "tiff" ]; askbot['data']['haveFlashNotifications'] = true; askbot['data']['activeTab'] = 'questions'; askbot['settings']['csrfCookieName'] = 'asksage_csrf'; askbot['data']['searchUrl'] = ''; /*<![CDATA[*/ $('.mceStatusbar').remove();//a hack to remove the tinyMCE status bar$(document).ready(function(){ // focus input on the search bar endcomment var activeTab = askbot['data']['activeTab']; if (inArray(activeTab, ['users', 'questions', 'tags', 'badges'])) { var searchInput = $('#keywords'); } else if (activeTab === 'ask') { var searchInput =$('#id_title'); } else { var searchInput = undefined; animateHashes(); } var wasScrolled = $('#scroll-mem').val(); if (searchInput && !wasScrolled) { searchInput.focus(); putCursorAtEnd(searchInput); } var haveFullTextSearchTab = inArray(activeTab, ['questions', 'badges', 'ask']); var haveUserProfilePage =$('body').hasClass('user-profile-page'); if ((haveUserProfilePage || haveFullTextSearchTab) && searchInput && searchInput.length) { var search = new FullTextSearch(); askbot['controllers'] = askbot['controllers'] || {}; askbot['controllers']['fullTextSearch'] = search; search.setSearchUrl(askbot['data']['searchUrl']); if (activeTab === 'ask') { search.setAskButtonEnabled(false); } search.decorate(searchInput); } else if (activeTab === 'tags') { var search = new TagSearch(); search.decorate(searchInput); } if (askbot['data']['userIsAdminOrMod']) { $('body').addClass('admin'); } if (askbot['settings']['groupsEnabled']) { askbot['urls']['add_group'] = "/s/add-group/"; var group_dropdown = new GroupDropdown();$('.groups-dropdown').append(group_dropdown.getElement()); } var userRep = $('#userToolsNav .reputation'); if (userRep.length) { var showPermsTrigger = new ShowPermsTrigger(); showPermsTrigger.decorate(userRep); } }); if (askbot['data']['haveFlashNotifications']) {$('#validate_email_alert').click(function(){notify.close(true)}) notify.show(); } var langNav = $('.lang-nav'); if (langNav.length) { var nav = new LangNav(); nav.decorate(langNav); } /*]]>*/ if (typeof MathJax != 'undefined') { MathJax.Hub.Config({ extensions: ["tex2jax.js"], jax: ["input/TeX","output/HTML-CSS"], tex2jax: {inlineMath: [["$","$"],["\$","\$"]]} }); } else { console.log('Could not load MathJax'); } //todo - take this out into .js file$(document).ready(function(){ $('div.revision div[id^=rev-header-]').bind('click', function(){ var revId = this.id.substr(11); toggleRev(revId); }); lanai.highlightSyntax(); }); function toggleRev(id) { var arrow =$("#rev-arrow-" + id); var visible = arrow.attr("src").indexOf("hide") > -1; if (visible) { var image_path = '/m/default/media/images/expander-arrow-show.gif?v=19'; } else { var image_path = '/m/default/media/images/expander-arrow-hide.gif?v=19'; } image_path = image_path + "?v=19"; arrow.attr("src", image_path); \$("#rev-body-" + id).slideToggle("fast"); } for (url_name in askbot['urls']){ askbot['urls'][url_name] = cleanUrl(askbot['urls'][url_name]); }