Math 2.0

definition

Induced 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.

Explanations

L1 human

Choose some vertices and keep all the edges between them. The result is the induced subgraph on those vertices.

What this node 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 node is. They do not measure its truth.

What this needs

To read this node, read these 3 nodes in this order. The foundations come first, and the list ends with this node.

Graph, definition, no evidence levelGraphdefinitionSubgraph, definition, no evidence levelSubgraphdefinitionInduced subgraph, definition, no evidence levelInduced subgraphdefinition
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Graph definition
  2. Subgraph definition
  3. Induced subgraph definition

Sources

  1. Web https://en.wikipedia.org/wiki/Induced_subgraph, Definition

What links here

No node links to this node yet.