# graph Flashcards

is a city on the Pregel river in Prussia

- The city occupied two islands plus areas on both banks

Kรถnigsber Bridge Problem

the greatest mathematician

that Switzerland has ever

produced

LEONHARD EULER

A branch of mathematics concerning with network of

points connected by lines (Carlson, 2020).

โข It is ultimately the study of relationships (Flovik, 2020).

mathematics of graph

: a region

A vertex

: a path(bridge) between two regions

An edge

A relation between an edge and a pair of vertices

graph

The number of vertices in G, ๐ฃ(๐บ)

order

The number of edges in G, ๐(๐บ)

size

๐ฝ(๐ฎ )

vertex set

๐ฌ(๐ฎ )

edge set

An edge whose endpoints are equal

loop

Edges have the same pair of endpoints

multiple edges

A graph has no loops or multiple edges

Simple graph

Two vertices are ___ and are ___if they are

the endpoints of an edge

adjacent, neighbors

a graph whose vertex set and edge set are

finite

finite graph

the graph whose vertex set and edges are

empty

null graph

the edges form

the same connections of vertices in each graph.

equivalent graphs

A simple graph

โข ๐(๐บโ) = ๐(๐บ)

โข ๐ธ(๐บโ) = { ๐ข๐ฃ | ๐ข๐ฃ ๏๐ธ(๐บ) }

complement

a set of pairwise adjacent vertices (a

complete subgraph)

Clique in a graph

a set of pairwise

nonadjacent vertices

independent set in a graph