Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

0
votes
2answers
115 views

non-Hamiltonian Cycles: How to Prove for Small Graphs

How do I prove that the following graph is a non-Hamiltonian cycle? $\hspace{5.3cm}$ I'm asked to create a graph which is both non-Eulerian and non-Hamiltonian, and this is what I produced in TiKz. ...
6
votes
1answer
403 views

A little fun with tournaments (graphs).

Assume $G$ is a tournament, i.e. a (finite) directed graph such that between any two vertices, $a$ and $b$, there is at least one edge in one of the two directions, $a\rightarrow b$ or $b\rightarrow ...
1
vote
3answers
64 views

Proving the existence of a unique planar embedding

Show that there is a unique planar embedding in which each vertex has degree 4 and each face has degree 3. It is easy to just draw such a planar graph, but how to show the embedding is unique? ...
2
votes
1answer
163 views

associativity in graph theory

Can anybody help me in clearing the facts how the associativity was proved in cartesian product of 3 graphs, and thus showing isomorphism. I can easily solve for the case when its two graphs. Taking ...
0
votes
1answer
129 views

How can I find the cut vertices from this graph?

$G = (\{a,b,c,d,e,f\}, \{\{a,b\}, \{b,c\}, \{c,d\}, \{d,e\}, \{e,f\}\})$ implies the following are cut vertices: a b c d e f Is each group of vertices in the list a ...
1
vote
2answers
130 views

Proving a fact about 4-regular graphs

Prove that 4-regular graphs have no bridges. How can I proceed? This has no solution on the textbook, and it is hard to think of any invariant or theorem involving 4-reg graphs in particular.
6
votes
2answers
282 views

Proving that a “prime graph” is connected

Let the prime graph be defined as the graph of all natural numbers, with two vertices being connected if the sum of the numbers on the two vertices add up to a prime number. Prove that the prime ...
0
votes
1answer
59 views

Graphs on surfaces other than the plane that are still $4$-colorable…?

In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus: I've learned ...
3
votes
1answer
347 views

How to get the adjacency matrix of the dual of $G$ without pen and paper?

Given the adjacency matrix $A$ of a $k$-regular planar graph $G$ with $V$ vertices, so $A$ has dimension $V$. How to get the adjacency matrix $\bar A$ of the dual of $G$ without drawing the dual ...
0
votes
2answers
545 views

Cut vertices and cut edges - did I answer these correctly?

Problem Find the cut vertices and cut edges for the following graphs My understanding of the definitions: A cut vertex is a vertex that when removed (with its boundary edges) from a graph creates ...
5
votes
6answers
8k views

prove that a connected graph with $n$ vertices has at least $n-1$ edges

Show that every connected graph with $n$ vertices has at least $n − 1$ edges. How can I prove this? Conceptually, I understand that the following graph has 3 vertices, and two edges: a-----b-----c ...
2
votes
1answer
722 views

Are my answers correct? (Graphs; paths; path lengths; circuits)

My answers a) Yes, this forms a path. This is a simple path. The length of this path is 4. b) Yes, this forms a path. This is a circuit. The length of this path is 4. c) Yes, this forms a ...
2
votes
1answer
45 views

Matrix and graphs

Prove that $G$ and $G'$ are isomorphic iff exists a matrix of permutations $P$ such that $A_{G'}=PA_{G}P^{T}$ Note: A matrix $P$ is called matrix of permutations if its entries are $0$ and $1$ and ...
1
vote
1answer
30 views

$9$ Vertices Each with $\deg(v_i)=3$

Can nine vertices be connected so that only three edges are incident upon all of them
0
votes
1answer
86 views

Is it possible to draw this graph?

Is it possible to draw a general graph with degree sequence $(4; 4; 2; 2; 3)$? Explain. Draw a graph that has vertex set $\{A, B, C, D, E\}$ and edge set $E=\{e_1=\{A, B\}, e_2=\{A, C\}, e_3=\{D\}. ...
3
votes
1answer
73 views

How one shows $K_{n,m}$ is not planar.

My professor is lecturing right now on how $K_{3,3}$ is not planar, where planar is defined as follows: Definition: A graph $G$ is called planar if it can be drawn in the plane without any two edges ...
1
vote
1answer
677 views

Prove that a simple planar bipartite graph on $n$ nodes has at most $2n-4$ edges.

By simple I mean no loops or double edges.
3
votes
1answer
97 views

Induced subgraph of subset graph?

For a natural number $N$ we can construct a graph $\underline{\text{SubsetGraph}}(N)$ with vertices for each subset of $\{1,2,\ldots,N\}$ and an edge between two vertices when the corresponding ...
0
votes
1answer
175 views

length of a walk in product graph

I was doing tensor product of graphs. We know that to find a walk between every two vertices x and y of any arbitrary length l in G, the graph must contain an odd cycle. I am stuck here. Is it ...
2
votes
1answer
501 views

Prove that if every node in a simple graph $G$ has degree $3$ or higher, then $G$ contains a cycle with a chord.

By simple graph I mean a graph with no loops or double edges. If $C$ is a cycle and $e$ is an edge connecting two non adjacent nodes of $C$, then $e$ is called a chord. I realize that one plan of ...
2
votes
1answer
81 views

new definition in graphs

I was reading a topic on wikipedia. There a product "corona product" was defined as : Corona product of graphs $G_1$ and $G_2$, is the graph which is the disjoint union of one copy of $G_1$ and ...
3
votes
5answers
5k views

How many edges does an undirected tree with $n$ nodes have?

How many edges does an undirected tree with $n$ nodes have?
5
votes
1answer
805 views

Four-color theorem from triangleless graphs

Prove that every planar graph without a triangle (that is, a cycle of length three) has a vertex of degree three or less. Then, prove that all planar graphs without triangles are four-colorable ...
3
votes
1answer
385 views

Why does my Barabasi Albert model implementation doesn't produce a scale free network

I'm trying to implement the Barabasi Albert model to generate some scale free network matching a power law distribution of degree. I'm using a value $m = 2$ for the main parameter of the algorithm, ...
3
votes
2answers
87 views

a basic doubt about definition in graph theory

Friends, I have a very basic doubt about neighborhood of a vertex. I was going through some pdf and their it was written about i-th neighbor of v, $v \in V(G)$. Can anybody explain me the term i-th ...
0
votes
1answer
115 views

clearing doubt over a definition

Can anybody tell me what is a Zig-Zag product in graph theory? I am getting no idea how this product is done and how edges are defined in the product? I have some links: ...
0
votes
1answer
120 views

Graph Help - Discrete Math

The vertices indicate where cashiers are located; the edges denote unblocked aisles between cashiers. The department store wants to set up a security system where (plainclothes) guards are placed at ...
0
votes
2answers
564 views

How to prove connectivity $\leq$ minimum degree?

For a simple graph (no loops or multiple edges), how to prove that the connectivity is equal to or smaller than the minimum degree? I just have no idea. I hope the answer could give me a general idea ...
3
votes
1answer
138 views

Finding a de Bruijn sequence from a graph

$DB_3$ is shown above. I used the Eulerian path: (000, 000, 001, 011, 111, 111, 110, 101, 011, 110, 100, 001, 010, 101, 010, 100, 000) and wrote down the labels of all the edges: 0111101100101000. ...
2
votes
1answer
43 views

One graph a subgraph of another?

Consider a graph $G$ on $n$ vertices with minimum degree $\delta$ and with its largest independent set $a>\delta$. Consider the graph $\bar{K}_a \otimes K_{n-a-1}$ (in other words, take a set of ...
1
vote
1answer
49 views

what is a flow in the context of the Ford-Fulkerson algorithm?

I am learning about the Ford Fulkerson algorithm, but having a hard time getting an intuitive feel for what a "flow" is. Is the "flow" the amount that travels between two adjacent nodes on a graph? Or ...
1
vote
1answer
68 views

Understanding proof of a theorem

I was going through the cartesian product of graph. There I read the following theorem.... First part of the proof is clear to me. Can anybody explain the converse part to me? I can't get it as ...
1
vote
1answer
115 views

Systematizing graph morphisms

Trying to systematize possible notions of graph morphisms I came about the following classification: A morphism $f$ which sends a graph $G$ to another graph $G'$ is – first of all – ...
0
votes
1answer
97 views

0 eigenvalue of weighted laplacian

I consider (weighted) directed graph and eigenvalues of its laplacian matrix. If a graph contains rooted out-branching which is the subgraph possessing a node can approaching to any nodes in the ...
3
votes
2answers
95 views

Is this graph a planar graph?

I am required to prove if this is planar or not. This is what I have tried. I have tried to form a $K_{3,3}$ or $K_5$ but I am unsucessful so far. I have also tried to use the formulas $e ≤ 3n - 6$ ...
4
votes
2answers
90 views

Automorphisms of a structure as a powerful tool for studying the structure

This is just an arbitrary testimony of an often repeated slogan: "The group of automorphisms of a given structure is often a powerful tool for studying this structure." D. Lascar, On the ...
11
votes
3answers
275 views

Coloring question

Consider any closed curve on the plane that does not repeat any segments, but possibly crossing itself at several points. How do I prove that the faces are $2$-colourable. For example: Help ...
0
votes
1answer
34 views

Is this graph transitive?

I have a graph $G = (A,B)$ which is transitive when: $(a,b) ∈ B ∧ (b,c) ∈ B → (a,c) ∈ B$. How can I prove that $G$ is transitive iff it's acyclic?
0
votes
1answer
21 views

Question about graphs and relations

If I have a directed graph $G = (V,E)$, let the relation $R$= {$(a,b)$ | $a$ has a directed path to $b$} be a relation over $V$. How can I prove that $R$ is an equivalence relation, partial order, ...
-1
votes
2answers
91 views

Simple Paths Along Vertices

Let $v$ and $w$ be distinct vertices in $K_n$, $n\geq 2$. Show that the number of simple paths from $v$ to $w$ is $$(n-2)!\sum_{k=0}^{n-2}\frac{1}{k!}.$$ A path with no repeated vertices is called a ...
-1
votes
1answer
110 views

Recurrence Relation Over Paths [closed]

Let $v$ and $w$ be distinct vertices in $K_n$. Let $p_m$ denote the number of paths of length $m$ from $v$ to $w$ in $K_n$, $1\leq m \leq n$. $(a)$ $\hspace{1cm}$Derive a recurrence relation for ...
2
votes
2answers
80 views

Graphing problem

Let $n ≥ 3$ be an integer, and let $S$ be a set of $n$ points on the plane such that the distance between any pair of points in $S$ is at least 1. Prove that there exists at most $3n - 6$ pairs of ...
1
vote
0answers
36 views

Possible number of endofunctors

The discrete category with countably many objects and morphisms has uncountably many endofunctors (= the number of functions from $\mathbb{N}$ to $\mathbb{N}$). Which categories with countably many ...
4
votes
2answers
534 views

Proving a graph is not bipartite

Let $G$ be a simple planar graph with at least $2$ vertices, and let $G^*$ be the dual of a planar embedding of $G$. Prove that if $G$ is isomorphic to $G^*$ , then $G$ is not bipartite. I have ...
2
votes
1answer
84 views

Proof for planar embeddings

Prove that any planar embedding of a simple connected planar graph contains a vertex of degree at most $3$ or a face of degree at most $3$. Can someone help me with this please? Thank you!
0
votes
2answers
202 views

Proving that a map formed by a closed curve is always 2-colorable

I need to prove that a closed curve on the plane, which forms a map using its intersections with itself, forms a 2-colorable map. How to approach this problem? I'm thinking of proving that the graph ...
0
votes
1answer
44 views

Split graph into groups of edges that are not adjacent

I need to split graph, another say to color it into some groups of unadjacent edges. Minimize number of groups is not the only goal to achive. Group of every size has its's own weight, e.g. 64 - 1, ...
0
votes
0answers
61 views

Medium-strong (graph) homomorphisms

Weak (graph) homomorphisms are mappings $f: V(G) \rightarrow V(G')$ such that the images of connected nodes $x,y$ (in the source graph) are connected: $$R(x,y) \rightarrow R(f(x),f(y)) = R(x',y')$$ ...
1
vote
0answers
37 views

Routing in a faulty hypercube

Suppose I colored a fraction (say $e$) of the edges of the $n$-dimensional hypercube. (the set $\{0,1\}^n$, with edges between points which differ by a single coordinate) Let $c<0$ be some ...
3
votes
0answers
188 views

How many paths (seen as subgraphs) of length $l$ are there in a given directed graph?

This question is similar to the one answered here but it's different for I'm defining paths as subgraphs, not sequences of vertices. Consider the definitions below. Definition 1. We call $G$ a ...