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
1answer
19 views

Graph Theory inequality

I've been trying to prove the following inequality If G is r-regular graph and $\kappa (G)=1 $, then $\lambda (G)\leq \left \lfloor \frac{r}{2} \right \rfloor$ I've tried manipulating the Whitney ...
0
votes
0answers
10 views

Labelling graph over an abelian group

I was reading about this equivalence of labellings on a graph where they mentioned about a group equivalence as a product of an automorphism with a labelling. I don't understand what kind of product ...
0
votes
0answers
13 views

Trees and Leaves (Graph Theory)

Let $T$ be a tree with $l$ leaves and $k \in \mathbb{Z}^{+}$ with $2k \geq l$. I need to show that there exists paths $P_{1}, P_{2},...,P_{k}$ such that: (i) $P_{1} \cup P_{2} \cup ... \cup P_{k} = ...
0
votes
0answers
23 views

How to find and prove the girth and circumference of the petersen graph

How to find and prove the girth and circumference of the Petersen graph? Does any one could help me? Thanks.
1
vote
3answers
40 views

Coloring simple graph

Given a graph with $5$ vertices and $6$ edges. Find the chromatic number and polynomial. The chromatic number is trivial, it would of course be $3$. But I am completely clueless on how to find the ...
0
votes
1answer
36 views

How to know if a graph exists or not?

Draw the required graph or explain why no such graph exists: 8-vertex, 2 component, simple graph with exactly 10 edges and three cycles. I think there is a graph but I'm not sure. Can anyone help to ...
0
votes
0answers
19 views

Criticise work with simple graphs & problem solving

So I'm studying graph theory at the moment and would like some constructive criticism or thoughts on my method. The problem can be formulated as follows. I'm looking for someone to verify my answer as ...
1
vote
1answer
13 views

Formal way of counting vertices

For a simple graph $G = (V,E)$ we know that there are $10$ edges, $|E|=10$. And we know that two vertices have a degree of $4$, and the rest have a degree of $3$. I know how to solve this, I'm just ...
1
vote
0answers
19 views

breaking a graph into two by removing 4 edges

Consider a simple planar 4-valent graph. I want to find out how to break it into two pieces by removing 4 edges, if such a way exists. Removing the four edges belonging to a single vertex doesn't ...
0
votes
0answers
23 views

Minimum Degree of a Graph

A graph $G = (V,E)$ satisfies $| E | <= 3 | V | - 6$. The min-degree of $G$ is defined as $\min \{\deg (v)\}$. Therefore, min-degree of G cannot be __ I don't know how to approach this problem . ...
0
votes
0answers
12 views

Dividing graph into branches

I would like to know an algorithm to produce a graph decomposition into branches with rank in the following way: ...
3
votes
1answer
20 views

Question about the proof that 'A graph with maximum degree at most k is (k + 1) colorable

I'm trying to follow the MIT introductory mathematics for cs course. In the reading on graph theory, the proof that a graph with maximum degree at most k is (k + 1) colorable is given as follows: ...
2
votes
0answers
56 views

Classification of maximally non-hamiltonian graphs?

A graph is called maximally non-hamiltonian, if it does not contain a hamilton-cycle, but no edge can be added without creating a hamilton-cycle. In other words, every pair of non-adjacent vertices ...
1
vote
1answer
71 views

Expected size of the connected component containing a randomly selected node

Given an Erdős–Rényi random graph with n nodes and edge probability p, what is the expected number of nodes in the connected component containing a randomly selected node? In other words, if I ...
2
votes
1answer
30 views

eigenfunctions on covering spaces of graphs

I am reading about lifts of graphs in relation to covering spaces. Before I pose my question I will explain some of the terminology. Let $G$ and $H$ be two graphs. We say that a function $f: V(H) ...
0
votes
0answers
13 views

Euler path line graphs and their duals?

Am having trouble drawing a dual of a given graph, I have tried it but I don'tvthink am correct. How should this question be done, below is also my trial;
1
vote
2answers
32 views

Is there a relationship between the clique of a graph and colouring of a graph?

Can one say that the minimum number of colours required to colour a graph (such that across any edge the two vertices have distinct colours) is lower bounded by the size of the maximum clique in the ...
0
votes
1answer
30 views

Resolving circular references in probability-graph

(Apologies, if the title is not accurate/useful, I'm not sure what else to call it... Ideas welcome...) Let's say I have a game that consists of several states S1, S2, S3, ... and coin-tosses that ...
3
votes
1answer
25 views

Let $T$ be a tree of order $n$.Show that $T$ is isomorphic to a subgraph of $\overline{C}_{n+2}$

Let $T$ be a tree of order $n$.Show that $T$ is isomorphic to a subgraph of $\overline{C}_{n+2}$ I'm allowed to use this theorem: for every tree $T$ of order $k$. If $G$ is a graph such that ...
1
vote
1answer
26 views

Let $G$ be a connected graph that is not a tree. Let $u,v \in V(G)$ such that $G-u$ and $G-v$ are both tree. Show that $deg(u)=deg(v)$

Let $G$ be a connected graph that is not a tree. Let $u,v \in V(G)$ , $u \not =v$ such that $G-u$ and $G-v$ are both tree. Show that $deg(u)=deg(v)$ Here is what I got so far. Let $T_1 =G-u$ and ...
2
votes
0answers
25 views

Is there a layer of abstraction on top of the graph?

Not sure if this is the most answerable question, but it is worth a shot. I am slowly getting into math, and have been interested in graph theory for a while. I use it in programming all the time. ...
2
votes
0answers
23 views

Generalization of Kneser's graph

Let's consider subsets of the set $\{1,\dots,n\}$ which consist of $m$ elements. I wonder, what is the maximal number of such subsets such that cardinality of intersection of any two of them isn't ...
0
votes
1answer
72 views

What proves clustering preserves DAG property?

English is not my first language so sorry for beeing unable to explain the situation as exactly as I would like to. I try to proof that if i got serial processes clustered, clusters are always ...
0
votes
2answers
30 views

In a Complete graph, prove $ \sum n_{i} = n, then { n_{i} \choose 2 } \le { n \choose 2 } $

I'm studying graphs in algorithm and complexity, but I'm not very good at math. In a Complete graph, prove $ \sum n_{i} = n, then { n_{i} \choose 2 } \le { n \choose 2 } $ ? please give some ideas.
1
vote
2answers
35 views

In complete graph, how can I prove ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$

I'm studying graphs in algorithm and complexity, but I'm not very good at math. How can I prove that ${n\choose 2} = {k\choose 2} + k(n-k) + {n-k\choose 2}$ for $0 \le k \le n$?
-1
votes
0answers
25 views

Cycle in 2 randon picks from k subset in s k-connect graph

Can you help me with this exercise ? Prove that a graph $G$ of order $n \geq k+1\geq 3$ is $k$-connected if and only if for each set $S$ of $k$ distinct vertices of $G$ and for each two-vertex ...
0
votes
0answers
53 views

Show that for every two vertices $u$ and $v$ of $3$-connected graph $G$, there exists two internally disjoint $u-v$ paths of different lengths in $G$

Can you help me with this exercise? I have no idea how to resolve it. A) Show that for every two vertices $u$ and $v$ of $3$-connected graph $G$, there exists two internally disjoint $u-v$ paths of ...
2
votes
0answers
47 views

Every graph G contains a path with d(G) edges (proof critique).

Curious to see whether my proof below is acceptable or not. Any feedback will be well received. Many thanks. Every graph G contains a path with $\delta(G)$ edges. $\mathbf{Proof.}$ Let $G$ be a ...
1
vote
2answers
120 views

Is this rule for graph isomorphism true?

Is it true that two graphs are isomorphic if they: Have the same number of vertices; Have the same degree for each vertex, that is a graph with degrees $(2,3,2,3)$ would be the same as a ...
-1
votes
2answers
19 views

How to prove that graph with 2 or more nodes has atleast 2 nodes which have same degree? [closed]

One of my instructor gave me a hint to use Pigeon-Hole principle, but I dont know how to apply this into this question.
4
votes
1answer
37 views

Understanding and interpreting graph spectra

I'm not a mathematician, but a geographer trying to get a grasp on some network analysis I'm experimenting with. I have a few questions related to spectral graph theory that a mathematician could help ...
1
vote
2answers
16 views

Given a node $x$ on a weighted graph, what algorithms are there for finding which node has the shortest path to $x$ from a given list of nodes?

Question: We are given this problem: On a weighted graph, a node $x$ and a set of nodes $L$, which of the nodes in $L$ has the shortest path to $x$? I would like to know if this problem has a faster ...
0
votes
0answers
25 views

An exercise of Diestel's book

Let $G$ be an infinite countable and connected graph that be not locally finite. By $\Omega(G)$, we mean the set of all ends of $G$. $\Omega(G)$ is compact if and only if for every finite set ...
0
votes
1answer
21 views

Proving G is 3 edge connected if G is connected graph and for every edge $e$, there are cycles $C_1$ and $C_2$ s.t. $E(C_1) \bigcap E(C_2) = \{e\}$

(1) If G is connected graph, and for every edge $e$, there are cycles $C_1$ and $C_2$ such that $E(C_1) \bigcap E(C_2) = \{e\},$ then $G$ is 3 edge connected. I'm trying to figure out how to prove ...
1
vote
0answers
20 views

Proving if G is a 3-regular graph, then the size of edge cut equals size of min size of vertex cut

https://noppa.aalto.fi/noppa/kurssi/t-79.5203/luennot/slides5.pdf.pdf on page 10 of 39 is the proof. It's theorem 4.1.11, which says "If G is a 3-regular graph, then $\kappa(G) = \kappa'(G)$", where ...
0
votes
0answers
10 views

Embeddings of a $2$-connected planar graph

Suppose, I have the adjacency matrix of a $2$-connected planar graph. The embedding might not be unique. How can I find out which embedding (or embeddings) the graph has without drawing it ? The ...
0
votes
0answers
26 views

Length of longest cycle in this graph

In the above graph, the blue line shows a cycle of length $84$, the remaining edges are higlihtged in red. In total, the graph has $100$ vertices and $143$ edges. Is this the longest cycle in this ...
0
votes
1answer
16 views

mapping two graphs

Consider two graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$. How to define a mapping function $f: V_1 \rightarrow V_2$ that preserves the adjacency in both graphs? EDIT: Thanks for answering! ...
0
votes
1answer
19 views

Prove that every connected graph of all whose vertices have even degree contain no bridges.

Prove that every connected graph of all whose vertices have even degree contain no bridges. I tried to prove this by induction. So let $G$ be a connected graph of order $n$. Since all vertices of $G$ ...
0
votes
1answer
17 views

Prove that if $deg(u)+deg(v)\geq n$ for every pair $u.v$ of non adjacent vertices of $G$, then $G$ is non-separable.

Prove that if $G$ is a graph of order $n \geq 3$ with property that $deg(u)+deg(v)\geq n$ for every pair $u.v$ of non adjacent vertices of $G$, then $G$ is non-separable. I'm trying to show that $G$ ...
2
votes
0answers
43 views

prove that if $C$ and $C'$ are any two $k-cycle$ in $G$, then $C$ and $C'$ have at lease 2 vertices in common.

Let $k$ be the maximum length of a cycle in a non-separable graph $G$ a) prove that if $C$ and $C'$ are any two $k-cycle$ in $G$, then $C$ and $C'$ have at least 2 vertices in common. b) Show that ...
0
votes
0answers
30 views

A question about similarity transformation.

Say $A$ is an $n\times n$ symmetric matrix such that every row (and hence column) has exactly $d<n$ non-zero entries. Does there exist similarity transformations on $A$ which will maintain these ...
0
votes
1answer
26 views

Eulerian Circuits

I have been tasked with coming up for algorithms for the following graphs if they are Eulerian: Cyclic - this is easy - All cyclic graphs are Eulerian and can be traversed in order from 1 to $n$. ...
1
vote
1answer
40 views

Prove that a 3-regular graph $G$ has a cut-vertex if and only if $G$ has a bridge.

Prove that a 3-regular graph $G$ has a cut-vertex if and only if $G$ has a bridge. Here is what I got so far <= Assume that $G$ is a 3-regular graph and $G$ has a bridge. Let $u,v \in V(G)$ ...
0
votes
0answers
61 views

What number is “b” in the following theorem?

In the following scientific paper (http://www.ggiakkoupis.name/papers/icalp14_dynamic.pdf?attredirects=0) I have read Theorem 1. (Site of George Giakkoupis: http://www.ggiakkoupis.name/, his papers: ...
3
votes
2answers
57 views

Coloring Graph with some constarints

if Graph G be a Cycle with Length=4. how many ways we can color this graph with at most $\lambda$ different color, in such a way that non of two adjacent vertex has a same color?
0
votes
1answer
8 views

Hamiltonian cycle on a subset of 2D points, constrained by a total length (traveling salesman variation)

We are given a list of 2d coordinates, each coordinate representing a node in a graph, and a scalar D, which is a constraint on total length of the cycle. The task is to find a Hamiltonian cycle on a ...
1
vote
1answer
23 views

directed graph and no directed cycles

Show that it is possible for a directed graph with $n$ vertices and no directed cycles to have $n(n−1)/2$ edges . I am approaching by saying $2$ vertices are required for $1$ edge, so total number of ...
1
vote
1answer
215 views

Is there software I can use to draw this graph?

So, I have this particular graph to consider. It has the vertex set $\{1,...,17\}$ and edge set $\{(i,j)|i+j ~\mbox{is prime}\}$. Define a cost function $c:E(G)\mapsto \mathbb{R}$ by setting ...
1
vote
1answer
10 views

Proving every 3-Regular graph with no cut-edge has a 1-factor

I have the proof in my textbook, but I'm stuck on a line (or two). Here's some context: Let $S \subseteq V(G)$. Count the edges between $S$ and the odd components of $G-S$, $o(G-S)$. Since $G$ is ...