﻿

Basics of Graph Theory, Connectivity, Walks

# Basics of Graph Theory, Connectivity, Walks

## Introduction

Here we are going to repeat basics of graphs, connectivity and walks.

## Objectives

• to study terminology about graphs;
• to revise main facts about basics of graphs;
• to know more about graph theory origin.

## Activity 1: Basic terms

You can revize terms by using flashcards.

## Instruction

Choose the correct term.

1. A graph which edges are ordered pairs of different nodes.

2. An edge whose endpoints are the same vertex.

3. Consider an edge e=ab of a graph (directed or undirected). The vertices a and b are ... with the edge e.

4. A vertex with degree 0.

5. A graph where all vertices are pairwise adjacent.

6. A subgraph of a graph G containing all vertices of G.

7.  A walk where first and last vertices are the same.

8. Two graphs that are not distinguished because they have the same structure.

9. An open walk in which all the edges are different.

10. The number of edges in the walk <u,v>.

## Activity 2: Some facts about graphs

To perform the task, you should know more then terms.

## Instruction

Marc correct and incorrect statements.

In a nontrivial simple graph...

the number of odd-degree vertices is even.
the number of even-degree vertices is even.
the sum of all vertex degrees is even.
the sum of all vertex degrees can be both even and odd.

For every bipartite graph having M vertices in one part and N vertices in another part ...

the sum of degrees is equal to MN.
the number of edges does not exceed MN.
the number of edges is even.
the sum of degrees of the vertices from one part is equal to the sum of degrees of the vertices from another part.

The number of non-isomorphic...

simple graphs of the order 5 is more than 20.
digraphs of the order 3 is less than 10.
multigraphs of the order 4 is less than 50.
simple graphs of the order 3 is less then 5.

For a simple graph with N vertices and K connectivity components,

the number of edges is not less than N-K.
the number of edges is less than N(N-1)/2.
the number of edges is not less than N(N-K)/2.
the number of edges is not more than N(N-K)/2.

A directed graph...

is either strongly connected or disconnected.
is weakly connected if it is strongly connected.
is unilaterally connected if it is weakly connected.
is weakly connected if and only if it is unilaterally connected.

A subgraph...

can be either proper or vertex-induced.
can be both proper and vertex-induced.
can be either proper or spanning.
can be either spanning or vertex-induced.

A walk can be either closed or open.
A path is also a trail.
A tour is also a cycle.
A chain does not include cycles.

## Instruction

Watch this video and fill the gaps with the words below. You can use a word more than once.

odd field even trivial two all lines new degree node Geometry graph mathematics Position seven route four degrees path point once mathematician more two

The two islands were connected to each other and to the river banks by bridges. Which could allow someone to cross all seven bridges without crossing any of them than ? Attempting to explain why led famous Leonhard Euler to invent a new of . of is now known as Graph Theory. The map could be simplified with each of the four landmasses represented as a single , what we now call a node, with , or edges, between them to represent the bridges. This simplified allows us to easily count the of each . The number of bridges touching each landmass visited must be Looking at the graph, it becomes apparent that all nodes have an degree. A Eulerian which visits each edge only once is only possible in one of scenarios. The first is when there are exactly nodes of degree, meaning all the rest are . The second is if the nodes are of even . The seemingly riddle led to the emergence of a whole field of mathematics.