Tagged Questions

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

-4
votes
0answers
21 views

$B=(V,E)$ is a tree. Show that you get a graph, if you add an edge. [on hold]

$B=(V,E)$ is a tree. Show that you get a graph which is not a tree, if you add an edge.
0
votes
0answers
7 views

Finding the cross boarders in plane graph

I have plane graphs. each node in the graph represent a planar polygon and edge indicate a certain relationship between planes. (I guess, it doesn't matter, we can represent any two variables by graph ...
2
votes
1answer
29 views

Best score in this puzzle

I want to maximise the score of the following table, choosing one item from each column/row, so no two items are on the same row or column. Score to maximise is just adding all the choices together. ...
0
votes
1answer
22 views

Why is the laplacian matrix for a graph positive semidefinite?

Why is the laplacian matrix for a graph positive semidefinite? Can anyone provide an intuitive explanation and a proof?
2
votes
0answers
12 views

Partitioning the plane into three sets each intersecting the vertices of every square with side 1 ?

Q1. Is it possible to partition the plane into three sets such that each of them contains at least one vertex of every square with side 1 ? Q2. Let $n$ be the largest integer such that the plane ...
1
vote
2answers
60 views

Is it possible to express the idea of a number bigger than any other number ($\infty$) in programming languanges? [on hold]

I'm studying graphs and algorithms, most of the algorithms we're using (such as Prim's algorithm), have the need of a table with a symbol $\infty$. Which in some contexts mean that it is the biggest ...
0
votes
0answers
29 views

How to prove isomorphism between these two graphs

I thought that the best way to approach this problem was to use a direct proof and say that since the graphs have the same number of vertices G1: {v1, v2, ..., vi, ..., vk} and G2 : {b1, b2, ..., ...
1
vote
0answers
21 views

Scheduling problem with two disjoint sets.

I have a scheduling problem for your sharp minds. I have a set A of Plumbers and a set B of clients. A plumber can visit multiple clients. A plumber must also end the day back home where they ...
-1
votes
0answers
20 views

Graph Theory Circulant Question [on hold]

Prove that a circulant graph with degree greater than or equal to 3 will have shortest cycle of at most 4.
0
votes
0answers
18 views

A plane triangulation is 3-connected: Proof

I want to prove: "A plane triangulation $G$ with at least 4 vertices is 3-connected" I have found this proof. I don't like it but I took some ideas out of it: ...
0
votes
1answer
17 views

Definition of connected graph

The definition of a connected graph states that: A graph $G$ is called connected provided for each pair $a,b$ with $a\neq b$ of vertices $\exists$ a walk joining a and b.(equivalently a chain joining ...
0
votes
2answers
41 views

Is there a simple graph with an odd number of automorphisms (except $1$ and $3$)?

The simple graphs upto $11$ vertices do not have $5,7,9,...$ automorphisms, in other words, the only odd numbers appearing are $1$ and $3$. Is this true for all graphs ? Formulated as an ...
0
votes
1answer
15 views

How to prove that path in directed tree is directed path?

So I have a directed tree where I have a path that begins in the root of tree and leads to any vertex. I have to prove that this path is a directed path.
7
votes
0answers
110 views

Math puzzle: 10 digit strings generations

There was a question in a math competition that I attended last year. At the end of competition, I realized that my answer was wrong for the question below and I have never been able to figure out how ...
0
votes
1answer
27 views

How to prove that graph has cycle?

Let $(V,E)$ be a graph where between each two vertices $v_1,v_2\in V$ there exists only one path. Then The graph has no cycles. Adding a new edge creates a cycle. I have no idea how it could be ...
0
votes
0answers
25 views

Probability that two doubletons are distinct in random graph

Let $G$ be a random graph with $K$ left nodes and $M$ right nodes. We have the following definition Definition: Two right nodes are called distinct if they are not connected to the same two left ...
2
votes
2answers
26 views

Proving that a graph is connected?

I'm trying to prove that this graph is connected given the provided information. Let $G$ be a simple undirected graph with $n \geq 2$ vertices. Prove that if $δ(G) \geq \frac{n}{2}$, then $G$ is ...
1
vote
0answers
19 views

Circulant Graph Definition

Question: If a circulant graph has $k$ vertices where k is odd and greater than 1, show that there are atleast $2k$ automorphisms? I am having trouble with the actual definition of circulant graphs. ...
0
votes
1answer
24 views

Definition of a tree and 2 cycles

I've run into a problem with the definition of a tree, and possibly more generally with the definition of a cycle. I've run into the problem a few sections after we talked about trees, and I never ...
1
vote
0answers
12 views

Natural properties of graph cycles that do not hold for circuits in a matroid?

In a graphic matroid $M(G)$, circuits correspond directly to cycles in the original graph $G$. This means that any property that can be defined for both a circuit in $M(G)$ and for a cycle in $G$ ...
0
votes
1answer
37 views

Expected number of connected singletons in random graph

Consider a random bipartite graph $G$ with $K$ left nodes and $M$ right nodes. Each of the $KM$ possible edges of the graph is connected with probability $p$ independently. I'm trying to compute the ...
1
vote
1answer
21 views

Lower Bound on the Number of Graph Isomorphism Classes

Are there any non-trivial lower bounds on the number of isomorphism classes for a graph with $N$ vertices? For example there are at least $N(N-1)/2$ isomorphism classes (counting one for the number ...
4
votes
1answer
38 views

Adjacency matrix and connectivity proof

Let $G$ be graph on $n$ vertices, $A$ its adjacency matrix, and $I_{n}$ the $n\times n$ identity matrix. Prove that $G$ is connected iff the matrix $(I_{n} + A)^{n-1}$ has no 0s. My proof: If the ...
1
vote
0answers
17 views

Properties of specific graph

In an application, I have to create a graph with $n$ specific types of nodes. A node of type $i$ has at most $e_i$ edges. Also, a stochastic matrix $P\in\mathbb{R}^{n\times n}$ is given. Now I ...
0
votes
0answers
35 views

On thinking that planarity is nothing but topology?

I've found the following quote on Harary's Graph Theory: And I'd like to know what it means. I know about the Kuratwoski theorem, which states that a graph is planar if no subgraph of it is ...
0
votes
1answer
25 views

Convert a tree to a forest where every component has an even number of vertices.

I have the following problem, which I am struggling with. It asks to find the maximum number of edges to be removed from a tree to convert it to a forest, where every component will have an even ...
1
vote
0answers
27 views

If two graphs have same number of vertex and both have Eulerian cycle, then they are isomorphic

Here is my proof: Suppose $ G_1 = (V_1, E_1) $ and $G_2 = (V_2, E_2)$. Then by the premise $$ \exists C_1 : i_1, i_2, \cdots, i_n=i_1, \forall i \in V_1$$ And $$ \exists C_2 : j_1, j_2, \cdots, ...
3
votes
1answer
27 views

Eulerian circuit with no isolated vertex is connected

This is my first question (ever), and I am pretty new to math. So I ask for patience and understanding in advance. So this is the proof I came up with: Consider $G = (V,E). $ By definition of ...
1
vote
0answers
10 views

Cumulants in diagrammatics (without physics or probability theory)

Formal cumulants ($\kappa_n$) and the associated moments ($\mu_n^{'}$) are related through log and exp transformations of exponential generating functions (e.g.f.): $$\exp \left [ \sum_{n=1}^{\infty ...
1
vote
1answer
19 views

For planar triangulation, equivalence between 4-connectedness and non existence of separating triangle.

I want to prove the following equivalence: "A planar triangulation is 4-connected if and only if it has no separating triangle." My attempts so far: $\Rightarrow$: If there is a separating ...
0
votes
1answer
26 views

How to prove $G$ is not Hamiltonian?

A connected graph $G$ of order $n=2k+1$ has $k+1$ vertices of degree 2, no two of which are adjacent, while the remaining $k$ vertices have degree 3 or more. Show that $G$ is not Hamiltonian.
0
votes
0answers
17 views

Adding an edge to a MST generated from a distance matrix

Given an $N\times N $ distance matrix, but not an adjacency matrix for a connected, weighted, undirected graph $G$, I've managed to find a minimum spanning tree (with $N - 1$ edges) using Prim's ...
0
votes
0answers
12 views

If a distance matrix is that of a weighted tree

I am given a distance matrix of size $n \times n$. I need to determine if it can represent a weighted tree or not.
1
vote
0answers
8 views

Measure of the clusters quality in a graph

Suppose we have a graph $G=(V,E)$ with $n$ non-overlapping subgraphs, the clusters $C_1, C_2, \dots, C_n$ which covers the graph $C_1 \cup \dots \cup C_n = G$. I'm looking for a good metric to ...
0
votes
0answers
30 views

How to draw a graph from edges [on hold]

If I have a set of edges and want to to plot the graph, what algorithm should I use? Each node has an id so it's kind of like projecting 1d points into 2d. I know that GNUplot can do this so I know ...
1
vote
1answer
15 views

Upper bound for the number of hamilton cycles in a cubic graph

Wikipedia states, that it has been proven, that there are at most $1.276^n$ hamilton cycles in a cubic graph with $n$ nodes. This upper bound is not valid for $n=6$. The values I found out using an ...
0
votes
0answers
17 views

Use the defect form of Hall's theorem to show G has a matching of size n/2

Hi and thanks in advance! Consider a bipartite graph G with vertex classes A and B. Assume that $$|A|=|B|=n \mbox{ where n is even}$$ $$\Delta (G) \leq 2\delta (G) $$ Use the defect form of Hall's ...
0
votes
2answers
48 views

How to prove that the diameter of a graph is less than 2 given that the minimum degree of any vertex in G is greater than the number of vertices / 2

How do I prove the following statement. Let $G = (V,E)$ be a graph. Prove that if $δ(G) \ge \frac{|V|}2$, then $\operatorname{diam}(G) \le 2$ I believe $\delta$ is minimum degree of any vertex ...
1
vote
0answers
25 views

Finding maximum independent set in sparse graph

Let $G=(V,E)$ be a directed graph such that each node has out-degree exactly $1$. What is an algorithm to find a maximum independent set? Is it possible to do this in $O(|V|)$ time? (Note that ...
0
votes
1answer
21 views

Dijkstra's algorithm - graph requirements

Short version of question: Can I use Dijkstra's algorithm to find the shortest path in non-planar graph? Long version: I'm working on an project in which I'm gonna find shortest path in a ...
0
votes
0answers
22 views

Incidence, adjacency and cocitation matrix

As homework we should create the adjacency, incidence and cocitation matrices of a simple graph. What are the differences between the adjacency and incidence matrices? Both show the relationships ...
1
vote
1answer
19 views

Prove that if $G$ has a Hamiltonian path then $k(G-S)≤|S|+1$ for every non-empty proper subset $S$ of $V(G)

State and prove a result analogous to theorem 3.16 that give a necessary condition for a graph to contain a Hamiltonian path. Theorem 3.16: If $G$ is Hamiltonian then $k(G-S) \leq |S|$ for every ...
1
vote
1answer
38 views

Show that $G$ is $3-$ordered Hamiltonian.

A Hamiltonian graph $G$ of order n is $k-$ordered Hamiltonian for an integer $k$ with $1≤k≤n$ if for every ordered set $S=\{v_1,v_2,…,v_k\}$ of $k$ vertices of $G$, there is a Hamiltonian cycle of $G$ ...
0
votes
1answer
15 views

Building a non-hamiltonian graph of $p$ vertices of $\frac{p-1}2$ degree each.

I want to build some graph with $p$ vertices all with degree of atleast $\frac{p-1}{2}$ that isn't hamiltonian. I imagine this is possible, but I can't seem to do it. Any suggestions? Perhaps looking ...
1
vote
0answers
15 views

Navigation in a graph

The problem Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$. We define the graph metric $d$ for ...
0
votes
0answers
13 views

Strong digraphs with no spanning subdigraph with fewer than $2n-2$ arcs.

Which strong digraphs $\mathcal{D}$ have no strong spanning subdigraphs with fewer than $2n-2$ arcs? I have seen this question in "Graph Theory (Graduate); Bondy, Murty", chapter 5, exercise 5.4.2.
1
vote
1answer
49 views

Existence of graphs when given the degrees of all vertices

My question is: How to decide whether a graph is exist when given the degree sequence of all vertices? This question can be easily reduced to the {0,1}-solutions of integer linear equation ...
0
votes
1answer
17 views

catching mole in at least move

Suppose that there are 4 hole on the soil surface and there is a mole underground. you want to cath this mole with a trap. if this mole rises to the surface using hole 2,a day later it rises to the ...
0
votes
1answer
19 views

What is the length of the longest decreasing sequence in integer matrix?

Given a finite $m \times n$ matrix $M$ with all distinct integers, we travel it following two simple rules: The travel can start from any cell, say, $M[i,j]$. At each cell $M[i,j]$, it computes the ...
1
vote
1answer
21 views

Lattice of a POSET Realtion

Given a set $S=\{1,2,3,4,5,6,7,8\}$, defined by a partial order relation Divisibility. Now consider all 4 elements containing sub-graphs, out of which $\{1,2,4,8\}$ is a Lattice obviously . Is ...