Largest induced tree

This file defines largestInducedTreeSize, the number of vertices in a largest induced subtree of a graph.

noncomputable def SimpleGraph.largestInducedTreeSize {α : Type u_1} (G : SimpleGraph α) : ℕ

largestInducedTreeSize G is the number of vertices in a largest induced subtree of G. A tree is a connected acyclic graph; an induced tree is an induced subgraph that is a tree.

Equations

• G.largestInducedTreeSize = sSup {n : ℕ | ∃ (s : Finset α), s.card = n ∧ (SimpleGraph.induce (↑s) G).IsTree}