Question

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

Short answer

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

Step-by-step solution

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.

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.