• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q2SE

Expert-verified
Found in: Page 738

Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

How many nonisomorphic subgraphs does $${{\rm{K}}_{\rm{3}}}$$have?

$${{\rm{K}}_{\rm{3}}}$$ has four nonisomorphic subgraphs.

See the step by step solution

Step 1: Definitions.

A whole graph A basic graph with $${\rm{n}}$$vertices and an edge between each pair of vertices are$${{\rm{K}}_{\rm{n}}}\left( {{\rm{n}} \ge {\rm{1}}} \right)$$.

$${{\rm{G}}_{\rm{1}}}{\rm{ = }}\left( {{{\rm{V}}_{\rm{1}}}{\rm{,}}{{\rm{E}}_{\rm{1}}}} \right){\rm{\& }}{{\rm{G}}_{\rm{2}}}{\rm{ = }}\left( {{{\rm{V}}_{\rm{2}}}{\rm{,}}{{\rm{E}}_{\rm{2}}}} \right)$$are two basic graphs being isomorphic if and only if there is a one-to-one and onto function $${\rm{f:}}{{\rm{V}}_1} \to {{\rm{V}}_{\rm{2}}}$$that makes $${\rm{a}}$$and $${\rm{b}}$$adjacent in $${{\rm{G}}_{\rm{1}}}$$if and only if $${\rm{f}}\left( {\rm{a}} \right)$$and $${\rm{f}}\left( b \right)$$are adjacent in$${{\rm{G}}_2}$$.

Step 2:To determine how many nonisomorphic subgraphs$${{\rm{K}}_{\rm{3}}}$$contains.

There are three vertices in $${K_3}$$and one edge between each pair of vertices.

$${K_3}$$subgraphs have the same vertices as $${K_3}\& 0,1,2,or3$$edges.

$${\rm{0}}$$edging:

A subgraph of $${K_3}$$is a graph of $${K_3}$$with no edges.

One edge:

A subgraph of $${K_3}$$is a graph containing precisely one of the three edges. Because renaming the vertices might result in the graph with one edge obtained below, any subgraphs of $${K_3}$$with one edge are isomorphic.

Two edgings:

A subgraph of $${K_3}$$is a graph containing exactly two of the three edges. Because renaming the vertices might result in the graph with two edges obtained below, any subgraphs of $${K_3}$$with two edges are isomorphic.

Three edges:

The subgraph $${K_3}$$is a subgraph of itself.

Step 3: Result.

The total number of nonisomorphic subgraphs of$${K_4}$$is four.

Three edges:

Two edges:

One edges:

Zero edge:

As a result, $${{\rm{K}}_{\rm{3}}}$$has four nonisomorphic subgraphs.