StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q2SE

Expert-verifiedFound in: Page 738

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.

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}\).

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.

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.

94% of StudySmarter users get better grades.

Sign up for free