Scribd
Upload
108 views9 pages

Subgraphs in Graph Theory Explained

A graph can have one and only one subgraph that is both spanning and induced - the graph itself. A spanning subgraph includes all the vertices of the original graph, while an induced subgraph includes all edges between the vertices it contains. Euler showed that it is impossible to traverse the bridges in Königsberg in a single path while crossing each bridge once, establishing the field of graph theory. A graph with an Eulerian cycle where a path exists visiting each edge once starting and ending at the same vertex is called an Eulerian graph; such a graph will have all vertices of even degree.

Uploaded by

subir123456
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
108 views9 pages

Subgraphs in Graph Theory Explained

A graph can have one and only one subgraph that is both spanning and induced - the graph itself. A spanning subgraph includes all the vertices of the original graph, while an induced subgraph includes all edges between the vertices it contains. Euler showed that it is impossible to traverse the bridges in Königsberg in a single path while crossing each bridge once, establishing the field of graph theory. A graph with an Eulerian cycle where a path exists visiting each edge once starting and ending at the same vertex is called an Eulerian graph; such a graph will have all vertices of even degree.

Uploaded by

subir123456
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Discrete Mathematics

GRAPH THEORY 2

Arindam Chakravorty
Subgraph

A subgraph G′ of a graph G is a graph whose set of vertices and set


of edges are all subsets of G.
Since every set is a subset of itself, every graph is a subgraph of itself.

G′ and G′′ and G itself are subgraphs of G.


Spanning Subgraph

A subgraph G′ of a graph G that has all the vertices of G is called a


spanning subgraph of G.

G′′ is a spanning subgraph of G while G′ is not .


A graph is a spanning subgraph of itself.
Induced Subgraph

A subgraph G′ of a graph G that has all edges of G corresponding to the


vertices in it is called an induced subgraph of G.

G G′
G′ is an induced subgraph of G.
A graph is an induced subgraph of itself.
An observation

Given a graph G, how many subgraphs can it have that are both spanning
and induced subgraphs of G?

A graph can have one and only one subgraph that is both a spanning
and an induced subgraph. – The graph itself
Number of Induced & Spanning Subgraphs

Given a graph G, with v number of vertices and e number of edges. How


many spanning subgraphs can it have? How many induced subgraphs can
it have?

Number of spanning subgraphs – There is no choice (only one way) on the


number of vertices (all of them have to be taken). We can choose none or
more of the e edges in 2e ways.

Number of induced subgraphs – We can choose none or more of the v


vertices in 2v ways. There is no choice (only one way) on the number of
edges (all the edges corresponding to chosen vertices have to be taken).

How many subgraphs can G have? – Is there a closed formula? Is there a


closed formula if the graph is of a given type (path, complete, cyclic, etc.)?
Königsberg Bridge Problem

Arrangement of bridges across the waters of the river Pregel River, which
surrounded three land masses connected by 7 bridges in old Prussian town
of Königsberg (now Kaliningrad, Russia).
A A

B D
B D

C
C
The question was can a person take a walk through the town in such a way
that each bridge would be crossed exactly once?
In 1735 the Swiss mathematician Leonhard Euler presented a solution to
this problem, concluding that such a walk is impossible.
Eulerian Trail, Eulerian Cycle, Eulerian Graph

Given a finite graph G, a trail (path) that traverses all edges exactly once
(vertices may be revisited) is called an Eulerian trail or Eulerian path.

An Eulerian trail that begins and ends at the same vertex is called
Eulerian Cycle or Eulerian Circuit.

A graph that has an Eulerian Cycle is called an Eulerian Graph.

Eulerian Graph

Not an Eulerian
A-B-C-D-E-F-G- Graph.
H-I-J-K is and
Eulerian Cycle
Eulerian Graph – A Litmus Test

Can we say whether a graph is Eulerian or not without explicitly finding an


Eulerian circuit?

A graph that has all vertices


of even degree is Eulerian
and vice versa.

Proof? – Left as an exercise

Eulerian Not Eulerian


All vertices All vertices do
have even degree not have even
degree

You might also like