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

2
votes
1answer
49 views

“Polysticks” in 3d

Consider a finite set of three-dimensional Euclidean vectors with integer components. How many three-dimensional closed loops can I construct with them? How many of them are elementary, i.e., cannot ...
0
votes
0answers
38 views

Is there a name for a graph homomorphism that is almost subgraph isomorphic but allows multiple nodes to map to the same node?

I'm looking for a kind of graph homomorphism $f : G = (V_G, E_G) \rightarrow H = (V_H, E_H)$ that is almost the same as subgraph isomorphism, but not quite. I require $f$ to map every node in $V_G$ to ...
0
votes
0answers
34 views

Connected vertex transitive graph with components

Let $G$ be locally finite connected vertex transitive graph and $S$ be a finite set of vertices of $G$ such that $G\setminus S$ has three components. Does exist $id\neq f\in {Aut}(G)$ such that $f(S)$ ...
0
votes
1answer
90 views

Prove that wheel (Wn) graph family are hamiltonian

I need to determine and prove that wheel (Wn) graph family are hamiltonian. I know that the Wn graphs are hamiltonian where it's possible to create a cycle that contains all the vertices, but How to ...
1
vote
1answer
370 views

Proof: How many edges need be removed from this graph to produce the spanning tree?

Assume the graph,$G$ has the degree sequence $6,4,4,3,3,3,3,2,2$. How many edges must be removed from $G$ to produce the spanning tree $T$? We can construct this graph using Havel-Hakimi's ...
0
votes
0answers
23 views

Proof verification that two spanning tress of the same graph are the same size

Let $H$ be any graph and $T_1$ and $T_2$ be spanning trees for $H$. Prove that the size of $T_1$ equals the size of $T_2$. Proof: $T_1$ has an edge set ...
0
votes
1answer
140 views

Prove that if $G$ is an nontrivial connected graph with at most 2 bridges, then there exists an orientation $D$

According to theorem 3.4, a nontrivial graph G has a strong orientation if and only if G is connected and contain no bridges a)Prove that if $G$ is an nontrivial connected graph with at most 2 ...
1
vote
1answer
100 views

Counting the number of complete bipartite subgraphs

I am stuck with problem and not getting much ideas. I have a graph with $N$ vertices and $M$ edges. I have to count number of ways I can choose a pair of set of vertices say $(p,q)$, such that every ...
0
votes
1answer
49 views

Orientation digraph question

Let $G$ be nontrivial connected graph without bridge a) show that for every edge $e$ of $G$ and for every orientation of $e$, there exist an orientation of the remaining edges of $G$ such that the ...
3
votes
0answers
67 views

Prove that a graph $G$ has an Eulerian orientation if and only if $G$ is Eulerian

Prove that a graph $G$ has an Eulerian orientation if and only if $G$ is Eulerian Here is what I got so far. => Let $G$ has an Eulerian Orientation, then $G$ is an Eulerian digraph. For any digraph ...
3
votes
1answer
68 views

Serial version of Hall's marriage theorem?

Hall's marriage theorem states that a collection of men can get married iff for every group of $k \geq 1$ men, the total number of women that like one or more of them is at least $k$. For example, if: ...
2
votes
4answers
675 views

What if not connectedness defines a graph?

I am studying graphs through an online course and came across the idea of a "connected component", a "subgraph in which any two vertices are connected to each other by paths, and which is connected to ...
3
votes
2answers
57 views

how many walks go through a given edge

Assume a symmetric matrix g of $0$'s and $1$'s that represents a non-directed graph with N nodes and assume there is an edge between nodes $i$ and $j$ (i.e. $g_{ij} = 1$). I am trying to count how ...
0
votes
1answer
37 views

Are These Graphs Circulant?

We will say a circulant graph is a graph whose adjacency matrix is circulant (even if the graph is disconnected). Let $R$ be a Dedekind domain, and let $I$ be an ideal of $R$ such that $R/I$ is finite ...
1
vote
1answer
123 views

Vertex degree and graph isomorphism

Suppose I have two simple graphs $G(V,E)$ and $H(V,E)$ with number of vertices $N$. And $\forall i \quad \text{such that}\quad 0<i<N$ No:of elements in $V(G)$ with degree $i $ = No:of elements ...
13
votes
1answer
204 views

What is the minimum number of vertices needed to represent a solid of genus $n$ in $\Bbb R^3$?

The image below shows a $9$-vertex polyhedron that is topologically equivalent to a torus, and hence has genus $1$. ...
3
votes
0answers
92 views

How to find the shortest path of a graph in a turing machine

I'm reading about Turing machine and I saw some examples as: Let $M_{1}$ a Turing Machine and the language $B = \{w\#w \vert w \in \{0,1\}^{*}\}$, We want $M_{1}$ to accept if its input is a member of ...
0
votes
1answer
58 views

Relation between nodes in a graph

i'm currently working on a mathproblem in "discrete mathematics for computing". I'm a little behind and have some trouble with one question. "Let ∼ be a relation defined on the nodes on a graph G(N, ...
1
vote
0answers
40 views

An Eulerian graph without an arbitrary trail is connected?

Let $G=(V,E)$ be an Eulerian graph. We say that a vertex $v$ in $V$ is a generator if every trail beginning in $v$ can be extended to form an Eulerian circuit. For this we will only consider simple ...
0
votes
1answer
173 views

For n≥3, n set of boys and girls has a stable matching (true or false)

For some n ≥ 3 there exists a set of n boys, n girls, and preference lists for every boy and girl such that every possible boy-girl matching is stable. If true, give a proof. If false, give a ...
0
votes
1answer
43 views

Show this tree exists for n >= 3

I wonder if you guys can help me find an easier solution for this. Show that for every n >= 3 a tree exists with exactly n nodes and n - 1 leaves. My instructor had a solution that basically ...
0
votes
3answers
113 views

Chess Board Coloring of a Paper using an Arbitrary Curve

Pick a piece of paper and a pen. Put the pen on a starting point and begin to draw an arbitrary curve and don't withdraw your hand until you reached the starting point. You can meet your curve during ...
1
vote
1answer
207 views

Bipartite Graph Matching Proof

You have a bipartite graph where the vertices are partitioned into 10 boys and 20 girls. Every boy vertex has degree 6. Every girl vertex has degree 3. Show that there exists a matching that matches ...
2
votes
1answer
45 views

Why can the complete graph $K_{16}$ be partitioned into three copies of the Clebsch graph?

The Clebsch graph is a $5$-regular graph on 16 vertices, defined as follows. Take the vertices and edges of the $4$-cube, and then add edges between antipodal pairs of vertices. Apparently, the edges ...
1
vote
1answer
91 views

Mutually Exclusive Definitions of Isomorphism?

Wolfram MathWorld defines Isomorphism: Let $V(G)$ be the vertex set of a simple graph and $E(G)$ its edge set. Then a graph isomorphism from a simple graph G to a simple graph H is a bijection ...
0
votes
1answer
88 views

A graph with infinitely many distinct cycles

I am trying to show the following statement, but I can't. If a graph contains infinitely many distinct cycles then it contains infinitely many edge-disjoint cycles.
0
votes
2answers
110 views

Is there a problem more difficult than NP-complete in graph theory?

There are some decision problems being NP-complete in graph theory, including the problem of deciding if a graph has a hamilton cycle, or determing the chromatic number. Since the number of labeled ...
4
votes
1answer
1k views

Suppose that every vertex of $G$ has degree at least 3. Prove that $G$ has a cycle of even length.

I've been working through some graph theory problems and recently encountered one which had me stumped. Fortunately, a solution was provided by my resource. Unfortunately, the solution does not seem ...
2
votes
2answers
180 views

Determine a formula for the number of triangles in the line graph $L(G)$ in term of quantities in $G$

Determine a formula for the number of triangles in the line graph $L(G)$ in term of quantities in $G$ I know that the line graph $L(G)$ of $G$ is a graph whose vertices are one to one correspondence ...
1
vote
1answer
65 views

Show that if $G$ is a connected graph of order $n≥2$ and $k$ is an integer with $1≤k≤n-1$, then $G^k$ is $k$-connected.

Show that if $G$ is a connected graph of order $n≥2$ and $k$ is an integer with $1≤k≤n-1$, then $G^k$ is $k$-connected. I'm not sure if I'm on the right track, but I tried to prove this by induction ...
2
votes
0answers
74 views

Spanning tree with infinitely many chords.

First, let me remind chord of graph. An edge which joins two vertices of a cycle but is not itself an edge of cycle is chord of that cycle. Now, I want to show that if a graph has spanning tree with ...
0
votes
1answer
22 views

Connecting nodes under certain conditions and trying to find the correct sequence on OEIS to describe the situation.

I would like to construct graphs under the following conditions: No loops Maximum of one edge between any nodes Connected No intersection between the edges may occur on a plane. Now, a similar ...
1
vote
1answer
102 views

Paper claiming a graph isomorphism that isn't actually an isomorphism?

This seems like it shouldn't be a problem, but here we are. In 'McKay’s Canonical Graph Labeling Algorithm': http://www.math.unl.edu/~aradcliffe1/Papers/Canonical.pdf on page 6, we have figure 1, a ...
2
votes
1answer
34 views

Smallest non-isomorphic graphs with the same characteristic polynomials of their laplacian matrices

For isomorphic graphs, the characteristic polynomials of their laplacian matrices coincide, but the converse is not true. The characteristic polynomial of the laplacian matrix does not uniquely ...
0
votes
0answers
34 views

Upto which number of vertices does every graph have a name?

I have heard of many families of graphs and also many famous graphs named after persons who intensively studied it. But I did not find a complete list with the names of the graphs to, lets say, ...
1
vote
1answer
57 views

Determine all connected graph $G$ such that subdivision graph $S(G)$ is Hamiltonian

Determine all connected graph $G$ such that subdivision graph $S(G)$ is Hamiltonian The subdivision graph $S(G)$ of a graph $G$ is that graph obtained from $G$ by replacing each edge $e=uv$ of $G$ ...
1
vote
1answer
96 views

Determine the formula for the toughness of a tree

Determine the formula for the toughness of a tree Here is what I got so far. Since every tree $T$ has at least 2 leaves, if we remove any vertex that adjacent to one of these leaves, we will get a ...
3
votes
4answers
476 views

Prove $\chi(G)\chi(\bar{G}) \geq n$ for chromatic number of graph and its complement

Let us denote by $\chi(G)$ the chromatic number, which is the smallest number of colours needed to colour the graph $G$ with $n$ vertices. Let $\bar{G}$ be the complement of $G$. Show that (a) ...
1
vote
1answer
87 views

Investigating properties of complements of paths

Take the first $n$ natural numbers. Construct a vertex-labeled graph with a vertex for each number. Now, connect any two vertices $a,b$ with an edge iff $a \pm 1 \neq b$. As Perry Iverson pointed ...
3
votes
1answer
196 views

Graph problem…

Let $D=(V,A)$ be a directed graph, and $s,t \in V$. Let $f:A \to \mathbb{R}_+$ be an $s$-$t$ flow of value $\beta$, show that there exists an $s$-$t$ flow $f':A\to\mathbb{Z}_+$ of value ...
1
vote
1answer
55 views

What is the chromatic index of a complete graph with its edges doubled?

If $G$ is a graph, let $G'$ denote the graph obtained by doubling each edge of $G$. How can I show that $\chi'(G')=2\chi'(G)$? I am considering the two cases when $G$ is a complete graph $K_n$ with ...
1
vote
2answers
92 views

Prove that no bipartite graph of order $3$ or more is Hamiltonian connected

Prove that no bipartite graph of order $3$ or more is Hamiltonian connected A graph $G$ is Hamiltonian connected if for every pair $u,v$ of vertices of $G$, there is a Hamiltonian $u-v$ path in ...
1
vote
1answer
16 views

Show that for every non-negative rational number $r$, there exist a graph $G$ with $t(G)=r$

a) Determine the toughness of the compete $k$-partite graph $ K_{n_1,n_2,…,n_k }$ where $n_1≤n_2≤⋯≤n_k$ b) Show that for every non-negative rational number $r$, there exist a graph $G$ with ...
1
vote
1answer
26 views

Show that if $G$ is a noncomplete graph of order $n$, then $t(G)≤\frac {n-α(G)}{α(G)}$

Show that if $G$ is a non-complete graph of order $n$, then $t(G)≤\frac {n-α(G)}{α(G)}$ with $\kappa(G)$ is connectivity of $G$, $\alpha (G)$ is the independent vertices of $G$, and $t(G)$ is the ...
0
votes
2answers
1k views

Can I use Dijkstra's Algorith for finding ALL shortest paths?

Suppose I know by promise that there are lots of paths from $v_s$ to $v_e$ in some graph $G \ni v_i$. Is there a way to modify Dijkstra's algorithm to find all shortest paths rather than just one ...
0
votes
1answer
25 views

Expressing the order o f a planar graph with two properties.

Let $G$ be a plane graph of order $n$ and size $m$ for which the boundary of every interior region of $G$ is a triangle, and the boundary of the exterior region is a $k$-cycle, ($k>2$). What is $m$ ...
3
votes
0answers
125 views

Split a graph on order to solve min cut max flow algorithm in parallel

I'm working with very big graph (millions of nodes) that have this structure: I'd like to solve the maximum flow/minimum cut problem in parallel by splitting the graph into multiple parts in order ...
0
votes
0answers
27 views

Least graph containing every connected graph with $m$ nodes as an induced subgraph

What is the smallest graph that contains every connected graph with $m$ nodes as an induced subgraph ? If the graph has $n$ nodes, there are $\binom{n}{m}$ (not necessariliy distinct) subgraphs with ...
0
votes
1answer
67 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. ...
1
vote
1answer
304 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?