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

3
votes
0answers
450 views

Showing equivalency between vertex disjoint and edge disjoint path problems in undirected graphs

First, here are the definitions I am working with: Given an undirected graph $G = (V,E)$ and vertices $s, t \in V$ we wish to either find the number of vertex disjoint paths from $s$ to $t$ or to find ...
1
vote
1answer
38 views

Does irreflexivity guarantee acyclicity?

Assume $R$ to be an irreflexive, transitive relation over a set $X$. Let $G=(X,E)$ be its directed graph where $(x,\hat{x})\in E$ if $xR\hat{x}$ is true. I know irreflexivity means $xRx$ cannot ...
1
vote
0answers
311 views

Rigorously prove that a u-v walk implies a u-v path of equal or lesser length .

I am trying to prove the following as an unofficial exercise for a course I'm in: Walks and paths in a graph Prove: For any graph if there is a k-length walk between two nodes, then there exists a ...
1
vote
1answer
64 views

Most efficient way to solve this combination problem

I have 4 very large list (l1, l2, l3, l4) of components (approx 9 million items in each list). Each list item has a cost and a value. I want to know how I can achieve the maximum combined value for ...
2
votes
1answer
421 views

Edge Coloring a Complete Graph.

The problem is: Find all natural numbers $n$ for which edges of a complete graph $K_n$ can be colored red and blue so that each vertex of a complete graph has an equal number of red and blue edges? ...
1
vote
1answer
46 views

Finding maximum flow of directed network with two inputs

I am given a directed network graph with three fixed verticess where two of these are "inputs" and and one is the "sink". I'm asked to find the maximal flow through the network. How should go about ...
0
votes
1answer
31 views

Prove that in every digraph $D$, some strong component has no entering edges and some strong component has no exiting edges.

I've been trying to prove the following result in "Introduction to Graph Theory (2'nd edition) by Douglas B. West": Prove that in every digraph $D$, some strong component has no entering edges and ...
2
votes
0answers
112 views

How many independent K-Plexes there are in a graph

K-plex - A k-plex is a relaxation of the clique problem. where each vertex needs to have ties to all but k other members. Assuming I have a k-plex. I need to count the number of distinct maximal ...
1
vote
1answer
43 views

Number of vertices with degree more than $\sqrt{|E|}$

Playing around, it seems for graph $G$ there is most $\sqrt{|E|}$ vertices with degree more than $\sqrt{|E|}$. Using sum of degrees is proof at most $2\sqrt{|E|}$ such vertices. But I cannot find ...
1
vote
0answers
30 views

how to prove that every complex circuit is a union of simple circuits

I have an euler circuit in a graph, and I want to prove that in-degree=out-degree. I know that if I can split the original circuit to simple ones, then every simple circuit has in-degree=out-degree. ...
1
vote
1answer
46 views

Rotors in graphs and rank polynomial (Tutte polynomial)

I am studying the $Rank$ $polynomial$ through matroid theory. I have seen that the rank polynomial doesn't determine the graph. In fact, as the the cycle matroid of a graph can distinguish the graph ...
1
vote
3answers
188 views

Numbers of ways $k - 1$ edges to be added to $k$ connected components to make the graph connected

Given a graph $G$ with $n$ vertices and $m$ edges. Let us say it has $k$ connected components. Find out how many numbers of ways you can add $k - 1$ edges to make the graph connected. Is it any ...
2
votes
1answer
114 views

Is it possible to know if such path in a graph exists?

Given a directed graph $G$, a node $n \in G$, is it possible (besides bruteforcing for all possible solutions) to know if there exists a path starting from the node $n$ and such that we visit each ...
0
votes
1answer
45 views

Connected Graph Statement

Every connected graph $G$ of order $4$ or more contains three distinct vertices $u$, $v$ and $w$ such that $G-u$, $G-v$ and $G-w$ are connected. Why is this statement false? Is there a ...
1
vote
0answers
30 views

Can't figure out how to prove Eulerian circuit

I have a graph that is undirected, connected and every vertex has an even degree and I want to prove that a graph like that has a circuit that goes through all edges and only once. I searched the ...
1
vote
2answers
51 views

Is it possible to build this graph?

Is it possible to build a graph made from 10 vertices, that has these degrees for each vertex? 1,2,1,2,3,4,3,4,5,6 it can be directed or un-directed, also it can be connected or not connected. ...
0
votes
1answer
51 views

Vertices, Edges and Line Segment intersection points

So, I have a bunch of graph edges defined by start and end vertices i.e. edge = (startVertex, EndVertex). No coordinates i.e x or y points provided. How do I ...
1
vote
2answers
68 views

Connected Graph

Prove that if $P$ and $Q$ are two longest paths in a connected graph, then $P$ and $Q$ have atleast one vertex in common. If I assume to the contrary that there are no vertices in common how can I ...
2
votes
1answer
219 views

shortest distance between nodes in a prunned torus Network

I am not a mathematician, but I am facing some mathematical challenge. I came across such a network for the first time which is shown in this figure. I am not sure, but I think it is called as Prunned ...
2
votes
2answers
78 views

Measuring how “connected” nodes are in a network

I am an undergraduate studying economics and mathematics. I've never studied graph theory formally (only briefly in my spare time) and as such I don't have formal terms for what I'm clumsily trying to ...
4
votes
0answers
66 views

Can't understand why this doesn't satisfy Laman's theorem

Definition: http://en.wikipedia.org/wiki/Laman_graph The following graph (top of picture) has $12$ vertices and $2\cdot12-3 = 21$ edges. I've tested all $2^{12}$ subsets of vertices, and all ...
2
votes
2answers
777 views

Any bipartite graph has a matching that covers each vertex of maximum degree

I need to prove following lemma: Any bipartite graph has a matching that covers each vertex of maximum degree Any help will be appreciated.
1
vote
2answers
82 views

How to go from Tree to Total orders

Given a tree $T=(X,E)$, is it guaranteed for any orientation of the edges $E$, there exist a strict total order preserves it? For instance, let $X=\{x_1,x_2,..x_n\}$ and $E=(x_i,x_{i+1})$ the result ...
1
vote
1answer
108 views

Number of 2n-1 equal size partitions up to symmetry

Consider the $K_{2n}$ (or just the set $\{1,\dots,2n\}$) with $S_{2n}$ acting on the vertices. Moreover consider a collection of 2n-1 partitions of the vertices into two equal sized sets (repeated ...
1
vote
1answer
31 views

Is there a proper name for a directed graph with one source and one destination?

The question says it all. Is there a name for a specific type of directed graph which contains only one source and one destination?
-2
votes
1answer
124 views

Union of two matchings that have same number of edges in each component

Let $G=(V,E)$ be a graph with a Hamiltonian path(or cycle) $P$. For any matching $M$ of the graph, is it always possible to find a matching $M'$ of $P$, such that every component of $G'=(V,M\cup M')$ ...
0
votes
1answer
131 views

Graph Theory: Isomorphic graphs

Show that the inverse of an isomorphism of graphs is also an isomorphism of graphs. So I just started a graph theory course and am having a little trouble with one of the problems on the homework. I ...
1
vote
0answers
136 views

Upper and lower bound for travelling salesman path.

Let $G$ be a complete graph with weights. $MST(G)$ is the length of it's minimal spanning tree and $TSP(G)$ is the length of minimal travelling salesman path (length I suppose it's the sum of weights ...
1
vote
0answers
39 views

Number of touching triplets in hypersphere packing contact graph

I would like to know what is curently known about the number $N$ of touching-triplets involving a given vertex $V$ in the contact-graph of $d$-hypersphere packings. For $d=2$ and $d=3$, one has $N = ...
1
vote
1answer
203 views

Generalized geography in a directed graph with a perfect matching

Greography is a game where players take turns naming cities. Each city chosen must begin with the same letter that ended the previous city. The game begins with any starting city and ends when a ...
0
votes
2answers
33 views

Graphs, Hamiltonian graphs, nodes… don't know topic name

I've got an exam in a couple of hours and going over the questions on a past paper. If someone could check out my answer, i'd be extremely grateful.
3
votes
1answer
37 views

Genus of a finite simple undirected graph

Suppose $G$ is a finite simple undirected graph and it has subgraph $G_1,\dots,G_n$, where $n \in \mathbb{N}$, such that $E(G_i)\cap E(G_j)=\emptyset$, for $i\neq j$, where $E(G)$ is the set of all ...
4
votes
4answers
101 views

Klein four-group as automorphism group of a graph.

Every finite abstract group is the automorphism group of some graph. Can someone show an example of a graph whose automorphism group is isomorphic to the Klein four-group?
0
votes
1answer
49 views

Proving that a graph has a complete circle?

I have a graph that is Connected, un-direct and all of its vertices have even degree. So does this kind of graph have at least one complete circle? A complete circle is a circle that passes in all ...
1
vote
1answer
41 views

Geodetic number of Qn

I know that the Geodetic number of the $Q_n$ ( Hypercube ) graph is 2. Also, the two elements in $V(Q_n)$ which they are differ in all position will make a geodetic set of the graph. But, how to prove ...
1
vote
1answer
1k views

Proof of König's theorem

Let $G=(V,E)$ be a graph. $H\subseteq V$ is called a vertex cover of $G$ iff $(u,v)\in E\Rightarrow u\in H\vee v\in H$. Now let's assume $G$ is bipartite, i.e. $V=V_1 \cup V_2$ and $E\subseteq ...
2
votes
1answer
69 views

Counting problem (should use Cayley's formula)

How many trees above $V=\{1,2,3,4,5,6,7,8,9\}$ are there, such that $deg(4)=5$? I know I should use Cayley's formula somehow.
3
votes
3answers
190 views

Example of a simple graph isomorphic to a permutation group.

I'm taking a first course in graph theory this semester and I'm working trough Graph Theory with Applications by J.A. Bonday and U.S.R. Murty. I can't find an answer to question 1.2.12(f): (a) ...
1
vote
1answer
128 views

Prove the correctness of the following greedy algorithm for finding a minimal spanning tree.

I have to prove that the following algorithm finds the minimal spanning tree. Let $G$ be the graph were doing the procedure on, and all edges have different weights. Step 1: Sort the edges in ...
5
votes
3answers
144 views

Maximum number of edges that a bipartite graph with $n,m$ vertices can have when it doesn't contain $4$-cycle

Let $A_{n,m}$ be the maximum number of edges that a bipartite graph with $n,m$ vertices can have when it doesn't contain $4$-cycle. I have calculated some values: $A_{2,2}=3$, $A_{3,3}=6$, ...
0
votes
2answers
379 views

Graphs with both Eulerian circuits and Hamiltonian paths

Which graphs have both Eulerian circuits and Hamiltonian paths, simultaneously? Honestly I don't know the level of the question. One of my friens asked me to put the question on math.stackexchange. ...
1
vote
0answers
49 views

Biconnected graph

Let $P$ be a piece of a bi-connected graph with respect to a cycle $C$. Show that if $P$ has at least one vertex, the number of edges of $P$ is greater than or equal to the number of attachments of ...
3
votes
2answers
120 views

Looking for counterexample in graph theory

I have this problem from graph theory: Given a graph $G = (V,E)$ (maybe with multiple edges) find if it's possible to delete some edges such that the new graph is 1-regular (ie. all of its vertices ...
4
votes
0answers
103 views

Graph composed of matchings and K_4

Let $G′ = (V, E_1 \cup E_2 \cup E_3)$ be a graph, where $E_1$ and $E_2$ are (nonempty) matchings and $E_3$ is the set of edges of a nonempty collection of pairwise vertex disjoint copies of $K_4$. ...
1
vote
1answer
133 views

Lower bound on the size of a maximal matching in a simple cycle

Let $C_n$ denote an undirected simple cycle of $n$ nodes. I want to determine a lower bound on the size of a maximal matching $M$ of $C_n$. Please note: A subset $M$ of the edges in $C_n$ is called a ...
1
vote
1answer
79 views

Graph Isomorphism property

I just started a graph theory course, and my very first homework problem is the following: If $ G \cong H $, show that $v(G) = v(H)$ and $e(G) = e(H)$. This is confusing to me, because (I think) ...
1
vote
1answer
198 views

Ramsey Number for Star graphs

For two graphs $H_1$ and H2, the Ramsey number $r(H_1, H_2)$ is the minimum number r so that in any red-blue coloring of the edges of the complete graph Kr on r vertices there is necessarily either a ...
3
votes
0answers
86 views

Representation theorems for graphs

Let $G = (V,E) = (V(G), E(G))$ be a graph, i.e. $V$ an arbitrary set, $E \subseteq \binom{V}{2}$ (undirected) or $E \subseteq V^2$ (directed). To be on the safe side, let me restrict to finite graphs. ...
7
votes
1answer
99 views

Quickest way to solve a matrix one step at a time.

I have a $14\times14$ matrix with a possibility of six states in each position The matrix is random each time. An example matrix would be: $$ \begin{pmatrix} ...
5
votes
2answers
360 views

Are resistor-battery networks always uniquely solvable?

Note: if you know the basics of circuits, feel free to skip the brief background; the question is at the bottom, starting below the triple horizontal rule. Most people with some physics background ...