Math 2.0

Combinatorics Definition

Induced subgraph

Builds on Subgraph

Definition

Let G=(V,E)G = (V, E) be a graph and let S⊆VS \subseteq V. The subgraph induced by SS is the graph G[S]G[S] with vertex set SS and edge set {{u,v}∈E:u,v∈S}.\{ \{u, v\} \in E : u, v \in S \}. A subgraph of this form is an induced subgraph.

Remarks

An induced subgraph is a subgraph that keeps every edge of GG between its vertices. In K4K_4, every subgraph induced by 33 vertices is a triangle. A path on these 33 vertices is a subgraph, but it is not induced. A clique induces a complete graph, and an independent set induces a graph with no edges.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph
Graph, definition, no evidence levelGraphdefinitionSubgraph, definition, no evidence levelSubgraphdefinitionInduced subgraph, definition, no evidence levelInduced subgraphdefinition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Graph definition
  2. Subgraph definition
  3. Induced subgraph definition

Where this leads

5 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Induced_subgraph, Definition
About this page
Tag0V05FC4GKQ
URIm2://0V05FC4GKQ
Kinddefinition
WritingW1 stated
MSC05C99
DefinesInduced subgraph
UsesSubgraph

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge instance_of in: one example (0 of 1)
  • edge not_instance_of in: one non-example that fails one clause (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by