Show that every induced subgraph of a complete graph Kn is also a complete subgraph.
Answers
Explanation:
CUT AND PENDANT VERTICES AND THE NUMBER OF
CONNECTED INDUCED SUBGRAPHS OF A GRAPH
AUDACE A. V. DOSSOU-OLORY
Abstract. A vertex whose removal in a graph G increases the number of components
of G is called a cut vertex. For all n, c, we determine the maximum number of connected
induced subgraphs in a connected graph with order n and c cut vertices, and also charac-
terise those graphs attaining the bound. Moreover, we show that the cycle has the smallest
number of connected induced subgraphs among all cut vertex-free connected graphs. The
general case c > 0 remains an open task. We also characterise the extremal graph struc-
tures given both order and number of pendant vertices, and establish the corresponding
formulas for the number of connected induced subgraphs. The ‘minimal’ graph in this
case is a tree, thus coincides with the structure that was given by Li and Wang [Further
analysis on the total number of subtrees of trees. Electron. J. Comb. 19(4), #P48, 2012].
1. Introduction and Preliminaries
Let G be a simple graph with vertex set V (G) and edge set E(G). The graph G is said
to be connected if for all u, v ∈ V (G), there is a u − v path in G. An induced subgraph
H of G is a graph such that ∅ 6= V (H) ⊆ V (G) and E(H) consists of all those edges of
G whose endvertices both belong to V (H). The order of G is the cardinality |V (G)|, i.e.
the number of vertices of G; the girth of G is the smallest order of a cycle (if any) in G; a
pendant vertex (or leaf) of G is a vertex of degree 1 in G.
A general question in extremal/structural graph theory [2, 25, 29] is to find the minimum
or maximum value of a prescribed graph parameter in a specified class of graphs. Tur´an’s
theorem [29] dating back to 1941, characterises the n-vertex graphs with greatest number
of edges that contain no complete graph as a subgraph; this is probably the most classical
result in extremal graph theory. This question has been studied quite thoroughly for several
other parameters including the popular invariant number of subtrees of a tree (a connected
graph with no cycle). Substantial work has been reported in the literature on the number
of subtrees, see for example [1, 11, 15, 16, 17, 18, 26, 27, 32]. In recent works [5, 6], our
main purpose was to extend some extremal results on the number of subtrees of a tree
to more general classes of graphs such as connected graphs or unicylic graphs (connected
graphs with only one cycle). In [5], order is prescribed for the class of all connected graphs
and the class of all unicyclic graphs. Specifically, paper [5] characterises those graphs
2010 Mathematics Subject Classification. Primary 05C30; secondary 05C35, 05C05.
Key words and phrases. cut vertex, pendant vertex, induced subgraph, connected graph, extremal graph
structure, tree.
The author was partially supported by the National Research Foundation of South Africa, grant 118521.